2672. Number of Adjacent Elements With the Same Color
Problem Description
In this problem, we are given an array called nums
that has a length n
and is initialized with all elements being uncolored (value of 0
). We are also provided with a list of queries where each query is represented as [index_i, color_i]
. For each query, we are asked to color the element at index_i
in nums
with color_i
. After processing each query, we need to count the number of pairs of adjacent elements that have the same color and are not uncolored.
To clarify, we need to return an array where each element corresponds to a query from the given list, and it indicates how many pairs of adjacent elements in nums
are matching in color and not uncolored, after applying that query.
Intuition
The main challenge in this problem is efficiently updating the color counts after each query since looking at all elements after every query might be too slow. To optimize this, we can only focus on the element at index_i
that is being colored by the current query and its neighbors, since the rest of the array remains unchanged.
When we color nums[i]
with color_i
, we need to consider the following:
- If
nums[i]
was already colored (not zero) and had the same color as its neighbor(s), we had a pre-existing pair(s) of same-colored adjacent elements. Changing the color ofnums[i]
will break these pairs, so we should decrement our count by the number of such pairs. - After we recolor
nums[i]
, it might form a new pair(s) of same-colored adjacent elements if it matches the color of its neighbor(s). In that case, we should increment our count relative to the new pairs formed.
We avoid iterating over the whole array and keep a running total of the same-colored pairs. To implement this:
- Keep a variable
x
to count the total number of same-colored adjacent pairs at any given stage. - Iterate through the queries, and for each query:
- Check the existing color at
index_i
. If it is the same as the color of its left (ifi > 0
) or right neighbor (ifi < n - 1
), decrementx
for each match before updatingnums[i]
color, since it will break that pair. - Update
nums[i]
withcolor_i
. - Then, check if
nums[i]
formed a new same-colored pair with its neighbors after being recolored. If so, incrementx
for each new pair formed. - Record the current count
x
in theans
array, which corresponds to the state after the current query is processed.
- Check the existing color at
- Return the
ans
array once all queries have been processed.
Solution Approach
The solution follows a straightforward approach by keeping track of the current count of adjacent same-colored pairs as it processes each query. The main focus is on the effect each query has on the number of these pairs. To understand how the solution works, let's walk through the implementation steps with reference to the given solution code:
-
Initialize a list
nums
of lengthn
with all values set to0
to represent the uncolored array, andans
with the length of queries to store the result after each query. -
Initialize a variable
x
to0
. This variable will keep track of the number of adjacent same-colored (not uncolored) pairs present innums
at any point. -
Loop through each query provided in
queries
, wherek
is the index of the query, and(i, c)
represents theindex_i
andcolor_i
of that particular query:- If the element at
index_i
(nums[i]
) is already colored (not equal to0
) and has the same color as its left neighbor (nums[i - 1]
), it means we currently have a same-colored pair that will be broken by recoloring. So, decrementx
as this pair will no longer exist after the current query. - Similarly, if
nums[i]
has the same color as its right neighbor (nums[i + 1]
), and it's not uncolored, decrementx
as this pair will also be dissolved.
- If the element at
-
Now, apply the query. Color the element at
index_i
innums
withcolor_i
(nums[i] = c
). -
After applying the query, check for new same-colored pairs:
- If the newly colored
nums[i]
matches the color of its left neighbor (nums[i - 1]
), we should incrementx
, since a new same-colored pair has been formed. - Do the same for the right neighbor. If
nums[i + 1]
matches the new color ofnums[i]
, incrementx
again for this new pair.
- If the newly colored
-
Store the updated value of
x
intoans[k]
to reflect the current number of adjacent same-colored pairs after the execution of thek
th query.
The algorithm makes use of:
- Array Data Structure: To store the initial state of the array (
nums
) and the result after each query (ans
). - Looping and Conditional Logic: To iterate through the queries and apply the necessary updates based on adjacent element colors.
By focusing only on the immediate neighbors of the index being colored in each query, the solution avoids any unnecessary operations on the rest of the array, allowing for an efficient update of the same-colored pairs count after each query.
Here's the final template filled with the content:
The solution to this LeetCode problem uses an array to represent the initial state of uncolored elements and processes a series of coloring queries on the array. It leverages the efficiency of only considering the coloring impact on immediate neighbors to update the count of adjacent same-colored pairs after each query. Specifically, the solution implements the following steps:
1. Initialize an array `nums` to represent the uncolored elements and `ans` to store the number of same-colored adjacent pairs after each query.
2. Initialize a variable `x` to maintain a running total of the same-colored adjacent pairs.
3. Loop over each query, where `index_i` is the array index to be colored and `color_i` is the color to apply.
- Before changing the color, check if the current color at `index_i` forms same-colored pairs with its neighbors. If such pairs exist, decrement `x`.
4. Color the element at `index_i` with `color_i`.
5. Check if the newly colored element forms new same-colored pairs with its neighbors. If new pairs are formed, increment `x`.
6. Save the updated count `x` into the `ans` array corresponding to the current query's result.
The efficient check for pairs before and after each query allows the algorithm to maintain an accurate count without iterating through the entire array each time. The use of arrays, looping, and conditional statements are integral to the algorithm's implementation.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate how the solution works.
Suppose we have an array nums
with n = 5
elements, all initialized to 0
(uncolored). Let's consider queries = [[1, 3], [2, 3], [1, 3], [3, 1]]
.
-
After the first query
[1, 3]
, color index1
with color3
.nums
becomes[0, 3, 0, 0, 0]
. No adjacent pairs are matching, soans[0] = 0
. -
After the second query
[2, 3]
, color index2
with color3
.nums
now is[0, 3, 3, 0, 0]
. There is a new adjacent pair3,3
at indices1
and2
. So we have one matching pair.ans[1] = 1
. -
The third query
[1, 3]
asks us to color index1
with color3
again. But it's already color3
, so there is no change. The array remains[0, 3, 3, 0, 0]
, and the number of matching pairs is also unchanged.ans[2] = 1
. -
Finally, the fourth query
[3, 1]
asks us to color index3
with color1
.nums
changes to[0, 3, 3, 1, 0]
. Now, there are no adjacent pairs with the same color, as the new color at index3
has broken the existing pair.ans[3] = 0
.
We end up with the final ans
array as [0, 1, 1, 0]
.
Breaking this down step-by-step according to the solution approach:
-
Initialize
nums
as[0, 0, 0, 0, 0]
andans
as an empty array to hold the results after each query. -
Set
x
to0
. No matching pairs yet. -
Process the first query
(1, 3)
:nums[1]
is0
, updating it to3
does not break any pair, sox
remains0
.- Update
nums
to[0, 3, 0, 0, 0]
. - No new pairs, update
ans
to[0]
.
-
Process the second query
(2, 3)
:nums[2]
is0
, so again updating it to3
breaks no pairs, leavingx
as0
.- Update
nums
to[0, 3, 3, 0, 0]
. - A new pair
3,3
is formed, incrementx
to1
. - Update
ans
to[0, 1]
.
-
Process the third query
(1, 3)
:nums[1]
is already3
, updating it to3
changes nothing.nums
remains[0, 3, 3, 0, 0]
.- No pairs are broken or formed, so
x
stays1
. - Update
ans
to[0, 1, 1]
.
-
Process the fourth query
(3, 1)
:nums[3]
is0
, updating it to1
does not break any pairs, sox
remains1
.- Update
nums
to[0, 3, 3, 1, 0]
. - The existing pair
3,3
is now broken, so decrementx
to0
. - Update
ans
to[0, 1, 1, 0]
.
In the end, the ans
array reflects the number of matching adjacent pairs after each query, demonstrating how the solution efficiently processes queries to dynamically maintain the count of matching pairs.
Solution Implementation
1class Solution:
2 def colorTheArray(self, size: int, queries: List[List[int]]) -> List[int]:
3 # Initialize the array with zeros indicating no color.
4 array = [0] * size
5 # Initialize the answer list to store results of each query.
6 result = [0] * len(queries)
7 # Initialize a variable to track the number of adjacent pairs with the same color.
8 adjacent_same_color_count = 0
9
10 # Iterate over the queries to process them sequentially.
11 for query_index, (position, color) in enumerate(queries):
12 # Decrement the count if the current position has a color and
13 # the previous position's color is the same as the current color.
14 if position > 0 and array[position] and array[position - 1] == array[position]:
15 adjacent_same_color_count -= 1
16 # Decrement the count if the current position has a color and
17 # the next position's color is the same as the current color.
18 if position < size - 1 and array[position] and array[position + 1] == array[position]:
19 adjacent_same_color_count -= 1
20
21 # Increment the count if the previous position's color is the same as the new color.
22 if position > 0 and array[position - 1] == color:
23 adjacent_same_color_count += 1
24 # Increment the count if the next position's color is the same as the new color.
25 if position < size - 1 and array[position + 1] == color:
26 adjacent_same_color_count += 1
27
28 # Record the count in the result after processing the query.
29 result[query_index] = adjacent_same_color_count
30 # Update the color of the current position.
31 array[position] = color
32
33 # Return the result list after processing all queries.
34 return result
35```
36
37Note: To use this code, you would need to have the appropriate typing imports at the top of the file:
38
39```python
40from typing import List
41
1class Solution {
2 public int[] colorTheArray(int n, int[][] queries) {
3 int numQueries = queries.length; // Number of queries
4 int[] arrayColors = new int[n]; // Array to keep track of colors
5 int[] answer = new int[numQueries]; // Array to store answers
6
7 // Initialize count of pairs with same color
8 int sameColorPairsCount = 0;
9
10 // Iterate through all queries
11 for (int queryIndex = 0; queryIndex < numQueries; ++queryIndex) {
12 int position = queries[queryIndex][0]; // Position to color
13 int color = queries[queryIndex][1]; // Color to apply
14
15 // Decrease count if removing a pair of the same color to the left
16 if (position > 0 && arrayColors[position] > 0 && arrayColors[position - 1] == arrayColors[position]) {
17 --sameColorPairsCount;
18 }
19 // Decrease count if removing a pair of the same color to the right
20 if (position < n - 1 && arrayColors[position] > 0 && arrayColors[position + 1] == arrayColors[position]) {
21 --sameColorPairsCount;
22 }
23 // Increase count if creating a new pair of the same color to the left
24 if (position > 0 && arrayColors[position - 1] == color) {
25 ++sameColorPairsCount;
26 }
27 // Increase count if creating a new pair of the same color to the right
28 if (position < n - 1 && arrayColors[position + 1] == color) {
29 ++sameColorPairsCount;
30 }
31
32 // Store the new count after this query
33 answer[queryIndex] = sameColorPairsCount;
34
35 // Apply the new color
36 arrayColors[position] = color;
37 }
38
39 // Return the array with answers to the queries
40 return answer;
41 }
42}
43
1#include <vector>
2
3class Solution {
4public:
5 // Method that takes the size of the array (n) and a list of queries
6 // Each query is a vector with two integers: index i and color c
7 std::vector<int> colorTheArray(int n, std::vector<std::vector<int>>& queries) {
8 // Create an array (nums) of size n to keep track of the colors
9 std::vector<int> nums(n, 0);
10 // Create an array (ans) to store the answers to the queries
11 std::vector<int> ans;
12
13 // Variable to keep track of the number of adjacent pairs with the same color
14 int adjacentPairsCount = 0;
15
16 // Iterate through each query in queries
17 for (auto& query : queries) {
18 // Extract index (i) and color (c) from the query
19 int index = query[0], color = query[1];
20
21 // Check if the current index has a left neighbor with the same color
22 // and if its color is already set (value greater than 0),
23 // decrement the count of adjacent pairs
24 if (index > 0 && nums[index] > 0 && nums[index - 1] == nums[index]) {
25 --adjacentPairsCount;
26 }
27
28 // Check if the current index has a right neighbor with the same color
29 // and if its color is already set (value greater than 0),
30 // decrement the count of adjacent pairs
31 if (index < n - 1 && nums[index] > 0 && nums[index + 1] == nums[index]) {
32 --adjacentPairsCount;
33 }
34
35 // Set the color at the current index to the color specified in the query
36 nums[index] = color;
37
38 // Check if the new color at the current index creates a new adjacent pair
39 // with the left neighbor, increment the count of adjacent pairs
40 if (index > 0 && nums[index - 1] == color) {
41 ++adjacentPairsCount;
42 }
43
44 // Check if the new color at the current index creates a new adjacent pair
45 // with the right neighbor, increment the count of adjacent pairs
46 if (index < n - 1 && nums[index + 1] == color) {
47 ++adjacentPairsCount;
48 }
49
50 // Add the current count of adjacent pairs to the answers array
51 ans.push_back(adjacentPairsCount);
52 }
53
54 // Return the answers array after processing all queries
55 return ans;
56 }
57};
58
1function colorTheArray(n: number, queries: number[][]): number[] {
2 // Initialize the array representing the colors of the n elements
3 const colors: number[] = new Array(n).fill(0);
4
5 // This will store the answer to how many neighboring pairs match after each query
6 const result: number[] = [];
7
8 // Variable to track the number of matching neighbors
9 let matchingNeighbors = 0;
10
11 // Iterate over each query where each query is an array [index, color]
12 for (const [index, color] of queries) {
13 // Decrease matchingNeighbors count if the current color matches the previous
14 // and there was a color (not 0) before the change
15 if (index > 0 && colors[index] > 0 && colors[index - 1] === colors[index]) {
16 --matchingNeighbors;
17 }
18
19 // Decrease matchingNeighbors count if the current color matches the next
20 // and there was a color (not 0) before the change
21 if (index < n - 1 && colors[index] > 0 && colors[index + 1] === colors[index]) {
22 --matchingNeighbors;
23 }
24
25 // Change the color at the given index
26 colors[index] = color;
27
28 // Increase matchingNeighbors count if the new color matches the previous
29 if (index > 0 && colors[index - 1] === color) {
30 ++matchingNeighbors;
31 }
32
33 // Increase matchingNeighbors count if the new color matches the next
34 if (index < n - 1 && colors[index + 1] === color) {
35 ++matchingNeighbors;
36 }
37
38 // Add the current number of matching neighbors to the result array
39 result.push(matchingNeighbors);
40 }
41
42 // Return the result array
43 return result;
44}
45
Time and Space Complexity
Time Complexity
The presented algorithm iterates through the queries
list once, processing each query in what is largely a constant time operation. The primary operations within the loop include:
- Accessing and updating elements in the
nums
list based on index, which is anO(1)
operation. - Checking conditions and incrementing or decrementing
x
, which is also anO(1)
operation.
Since these O(1)
operations are all that occur in the loop and the loop runs for each query in queries
, the time complexity of the algorithm is O(q)
, where q
is the number of queries.
Space Complexity
The space complexity of the algorithm includes:
- The
nums
list which is initialized withn
elements, resulting inO(n)
space. - The
ans
list which is also proportional to the number of queriesq
, which makes itO(q)
space.
Since these two lists are not dependent on each other, the total space complexity of the algorithm is O(n + q)
, accounting for both the nums
array of n
elements and the ans
array of q
elements.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!