Number of Adjacent Elements With the Same Color

MEDIUM

Description

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] = [index_i, color_i]. For the i^th query:

Set colors[index_i] to color_i.
Count the number of adjacent pairs in colors which have the same color (regardless of color_i).

Return an array answer of the same length as queries where answer[i] is the answer to the i^th 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 1^st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
After the 2^nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
After the 3^rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
After the 4^th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
After the 5^th 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 1^st query colors = [100000]. The count of adjacent pairs with the same color is 0.

Constraints:

1 <= n <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= index_i <= n - 1
1 <= color_i <= 10⁵

Approaches

Checkout 2 different approaches to solve Number of Adjacent Elements With the Same Color. Click on different approaches to view the approach and algorithm in detail.

Optimized Approach: Incremental Update

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 colors of size n with all elements as 0.
Initialize an integer array ans of size queries.length.
Initialize a counter count = 0.
Iterate through each query [index, newColor] from i = 0 to queries.length - 1:
- Get the oldColor at colors[index].
- If oldColor is the same as newColor, the count doesn't change. Set ans[i] = count and continue.
- Check the left neighbor at index - 1 (if it exists):
  - If colors[index - 1] formed a pair with oldColor (and oldColor != 0), decrement count.
  - If colors[index - 1] forms a new pair with newColor, increment count.
- Check the right neighbor at index + 1 (if it exists):
  - If colors[index + 1] formed a pair with oldColor (and oldColor != 0), decrement count.
  - If colors[index + 1] forms a new pair with newColor, increment count.
- Update the color in the array: colors[index] = newColor.
- Set ans[i] = count.
Return the ans array.

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 Analysis

Time Complexity: 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 Complexity: O(n + q) to store the `colors` array of size `n` and the answer array of size `q`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Adjacent Elements With the Same Color. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Adjacent Elements With the Same Color

Data Structures:

Array

Companies:

Roblox |Visa |Capital One |