Number of Adjacent Elements With the Same Color
MedPrompt
You are given an integer n representing an array colors of length n where all elements are set to 0's meaning uncolored. You are also given a 2D integer array queries where queries[i] = [indexi, colori]. For the ith query:
- Set
colors[indexi]tocolori. - Count the number of adjacent pairs in
colorswhich have the same color (regardless ofcolori).
Return an array answer of the same length as queries where answer[i] is the answer to the ith query.
Example 1:
Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
Output: [0,1,1,0,2]
Explanation:
- Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.
- After the 1st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
- After the 2nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
- After the 3rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
- After the 4th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
- After the 5th query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.
Example 2:
Input: n = 1, queries = [[0,100000]]
Output: [0]
Explanation:
After the 1st query colors = [100000]. The count of adjacent pairs with the same color is 0.
Constraints:
1 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
Instead of re-calculating the entire count of adjacent pairs for each query, we can maintain a running count and update it based on the single change made by the query. A color change at index can only affect the pairs (colors[index-1], colors[index]) and (colors[index], colors[index+1]). By analyzing the state of these two pairs before and after the update, we can adjust the count in constant time for each query.
Algorithm
- Initialize an integer array
colorsof sizenwith all elements as 0. - Initialize an integer array
ansof sizequeries.length. - Initialize a counter
count = 0. - Iterate through each query
[index, newColor]fromi = 0toqueries.length - 1:- Get the
oldColoratcolors[index]. - If
oldColoris the same asnewColor, the count doesn't change. Setans[i] = countand continue. - Check the left neighbor at
index - 1(if it exists):- If
colors[index - 1]formed a pair witholdColor(andoldColor != 0), decrementcount. - If
colors[index - 1]forms a new pair withnewColor, incrementcount.
- If
- Check the right neighbor at
index + 1(if it exists):- If
colors[index + 1]formed a pair witholdColor(andoldColor != 0), decrementcount. - If
colors[index + 1]forms a new pair withnewColor, incrementcount.
- If
- Update the color in the array:
colors[index] = newColor. - Set
ans[i] = count.
- Get the
- Return the
ansarray.
Walkthrough
We maintain a running count of adjacent pairs, count, which is initially 0. For each query [index, newColor], we first identify the oldColor at colors[index]. The change at index can only affect its left neighbor (index-1) and its right neighbor (index+1).
Before updating the color, we check if colors[index] formed a pair with its neighbors. If index > 0 and colors[index-1] was paired with oldColor, this pair is now broken, so we decrement count. Similarly, if index < n-1 and colors[index+1] was paired with oldColor, we decrement count.
After accounting for broken pairs, we update colors[index] = newColor. Then, we check if the newColor forms new pairs. If index > 0 and colors[index-1] now pairs with newColor, we increment count. Likewise, if index < n-1 and colors[index+1] pairs with newColor, we increment count.
The updated count is the answer for the current query. This way, each query is processed in O(1) time.
class Solution { public int[] colorTheArray(int n, int[][] queries) { int[] colors = new int[n]; int[] ans = new int[queries.length]; int count = 0; for (int i = 0; i < queries.length; i++) { int index = queries[i][0]; int newColor = queries[i][1]; int oldColor = colors[index]; if (oldColor == newColor) { ans[i] = count; continue; } // Check left neighbor if (index > 0) { // If there was a pair with the old color, it's now broken if (colors[index - 1] != 0 && colors[index - 1] == oldColor) { count--; } // If a new pair is formed with the new color if (colors[index - 1] != 0 && colors[index - 1] == newColor) { count++; } } // Check right neighbor if (index < n - 1) { // If there was a pair with the old color, it's now broken if (colors[index + 1] != 0 && colors[index + 1] == oldColor) { count--; } // If a new pair is formed with the new color if (colors[index + 1] != 0 && colors[index + 1] == newColor) { count++; } } // Update the color in the array colors[index] = newColor; ans[i] = count; } return ans; }}Complexity
Time
O(q), where `q` is the number of queries. Each query involves a constant number of checks and updates, making the processing time for each query O(1).
Space
O(n + q) to store the `colors` array of size `n` and the answer array of size `q`.
Trade-offs
Pros
Highly efficient and optimal for the given constraints.
Processes each query in constant time, leading to a fast overall solution.
Cons
The logic is slightly more complex than the brute-force approach, requiring careful handling of edge cases (index 0 and n-1) and state changes.
Solutions
Solution
class Solution { public int [] colorTheArray ( int n , int [][] queries ) { int m = queries . length ; int [] nums = new int [ n ]; int [] ans = new int [ m ]; for ( int k = 0 , x = 0 ; k < m ; ++ k ) { int i = queries [ k ][ 0 ], c = queries [ k ][ 1 ]; if ( i > 0 && nums [ i ] > 0 && nums [ i - 1 ] == nums [ i ]) { -- x ; } if ( i < n - 1 && nums [ i ] > 0 && nums [ i + 1 ] == nums [ i ]) { -- x ; } if ( i > 0 && nums [ i - 1 ] == c ) { ++ x ; } if ( i < n - 1 && nums [ i + 1 ] == c ) { ++ x ; } ans [ k ] = x ; nums [ i ] = c ; } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.