Number of Adjacent Elements With the Same Color

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.

• 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;
    }
}