Number of Adjacent Elements With the Same Color

• 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.

1class Solution {2    public int[] colorTheArray(int n, int[][] queries) {3        int[] colors = new int[n];4        int[] ans = new int[queries.length];5        int count = 0;6        7        for (int i = 0; i < queries.length; i++) {8            int index = queries[i][0];9            int newColor = queries[i][1];10            int oldColor = colors[index];11            12            if (oldColor == newColor) {13                ans[i] = count;14                continue;15            }16            17            // Check left neighbor18            if (index > 0) {19                // If there was a pair with the old color, it's now broken20                if (colors[index - 1] != 0 && colors[index - 1] == oldColor) {21                    count--;22                }23                // If a new pair is formed with the new color24                if (colors[index - 1] != 0 && colors[index - 1] == newColor) {25                    count++;26                }27            }28            29            // Check right neighbor30            if (index < n - 1) {31                // If there was a pair with the old color, it's now broken32                if (colors[index + 1] != 0 && colors[index + 1] == oldColor) {33                    count--;34                }35                // If a new pair is formed with the new color36                if (colors[index + 1] != 0 && colors[index + 1] == newColor) {37                    count++;38                }39            }40            41            // Update the color in the array42            colors[index] = newColor;43            ans[i] = count;44        }45        46        return ans;47    }48}

• Initialize an integer array colors of size n with all elements as 0.
• Initialize an integer array ans of size queries.length.
• Iterate through each query [index, color] from i = 0 to queries.length - 1:
  • Update the array: colors[index] = color.
  • Initialize a counter count = 0.
  • Iterate from j = 0 to n - 2:
    • If colors[j] is not 0 and colors[j] is equal to colors[j+1], increment count.
  • Set ans[i] = count.
• Return the ans array.

We maintain an array colors of size n, initialized to all zeros. For each query [index, color], we first update colors[index] to the new color. Then, we reset a counter for adjacent pairs to zero. We iterate from the beginning of the colors array up to the second-to-last element. In each step of the iteration, we check if colors[i] is equal to colors[i+1] and is not zero (uncolored). If both conditions are true, we increment our counter. After the loop finishes, the counter holds the total number of adjacent pairs for the current state of the array. We store this count in our result array. This process is repeated for all queries.

1class Solution {2    public int[] colorTheArray(int n, int[][] queries) {3        int[] colors = new int[n];4        int[] ans = new int[queries.length];5        6        for (int i = 0; i < queries.length; i++) {7            int index = queries[i][0];8            int color = queries[i][1];9            colors[index] = color;10            11            int adjacentCount = 0;12            for (int j = 0; j < n - 1; j++) {13                if (colors[j] != 0 && colors[j] == colors[j+1]) {14                    adjacentCount++;15                }16            }17            ans[i] = adjacentCount;18        }19        20        return ans;21    }22}