# Number of Adjacent Elements With the Same Color
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-adjacent-elements-with-the-same-color)
Canonical: https://scaleengineer.com/dsa/problems/number-of-adjacent-elements-with-the-same-color
**Data structures:** Array
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one)
---
## Problem
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]` to `colori`.
* Count the number of adjacent pairs in `colors` which have the same color (regardless of `colori`).

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 <= 105`
* `1 <= queries.length <= 105`
* `queries[i].length == 2`
* `0 <= indexi <= n - 1`
* `1 <= colori <= 105`

# Approaches
## Brute Force: Re-computation for Each Query
This approach involves simulating the process directly. For each query, we update the color in the array and then iterate through the entire array to count the number of adjacent pairs with the same color. This is simple to implement but inefficient for large inputs.
**Time:** O(q * n), where `q` is the number of queries and `n` is the size of the array. For each of the `q` queries, we iterate through the `n` elements of the array. This will result in a Time Limit Exceeded (TLE) verdict for the given constraints. · **Space:** O(n + q) to store the `colors` array of size `n` and the answer array of size `q`.
**Pros:** Very simple and straightforward to understand.; Easy to implement without complex logic.
**Cons:** Highly inefficient due to re-calculating the count from scratch for every query.; Not feasible for the given constraints (`n` and `q` up to 10^5), leading to a Time Limit Exceeded (TLE) error.
### Explanation
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.

```java
class Solution {
    public int[] colorTheArray(int n, int[][] queries) {
        int[] colors = new int[n];
        int[] ans = new int[queries.length];
        
        for (int i = 0; i < queries.length; i++) {
            int index = queries[i][0];
            int color = queries[i][1];
            colors[index] = color;
            
            int adjacentCount = 0;
            for (int j = 0; j < n - 1; j++) {
                if (colors[j] != 0 && colors[j] == colors[j+1]) {
                    adjacentCount++;
                }
            }
            ans[i] = adjacentCount;
        }
        
        return ans;
    }
}
```
### Algorithm
- 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.

## 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.
**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`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: vector < int > colorTheArray ( int n , vector < vector < int >>& queries ) { vector < int > nums ( n ); vector < int > ans ; int x = 0 ; for ( auto & q : queries ) { int i = q [ 0 ], c = q [ 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 . push_back ( x ); nums [ i ] = c ; } return ans ; } };
```

### Python

```python
class Solution : def colorTheArray ( self , n : int , queries : List [ List [ int ]]) -> List [ int ]: nums = [ 0 ] * n ans = [ 0 ] * len ( queries ) x = 0 for k , ( i , c ) in enumerate ( queries ): if i > 0 and nums [ i ] and nums [ i - 1 ] == nums [ i ]: x -= 1 if i < n - 1 and nums [ i ] and nums [ i + 1 ] == nums [ i ]: x -= 1 if i > 0 and nums [ i - 1 ] == c : x += 1 if i < n - 1 and nums [ i + 1 ] == c : x += 1 ans [ k ] = x nums [ i ] = c return ans
```