Count Equal-Colored Neighbors After Each Recoloring
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Count Equal-Colored Neighbors After Each Recoloring
An array `colors` has length `n` and initially contains only zeros. Zero means that a position is uncolored.
Process `queries` in order. A query `[index, color]` assigns the positive value `color` to `colors[index]`, replacing any previous color there. After each query, count all adjacent position pairs whose two entries have the same **nonzero** color. Return these counts in query order.
A pair is counted by its positions: a run of three equal positive colors contains two adjacent pairs. Uncolored neighbors do not count, and the count includes every positive color rather than only the color in the latest query.
### Examples
**Example 1**
```text
Input: n = 5, queries = [[2,7],[1,7],[3,7],[2,4],[0,7],[4,7]]
Output: [0,1,2,0,1,2]
```
The successive arrays are `[0,0,7,0,0]`, `[0,7,7,0,0]`, `[0,7,7,7,0]`, `[0,7,4,7,0]`, `[7,7,4,7,0]`, and `[7,7,4,7,7]`.
**Example 2**
```text
Input: n = 3, queries = [[0,9],[2,9],[1,9],[1,9],[1,2]]
Output: [0,0,2,2,0]
```
The middle position first joins two equal-colored neighbors, is then assigned its existing color again, and finally separates those neighbors by becoming color `2`.
### Constraints
- `1 <= n <= 100000`.
- `1 <= queries.size() <= 100000`.
- Every query contains exactly two integers.
- `0 <= index <= n - 1`.
- `1 <= color <= 100000`.
### Clarifying Questions
- Can a position be recolored repeatedly? Yes, including reassignment to the same color.
- Do two zeros form a matching pair? No; zero denotes an uncolored position.
- Are pairs disjoint? No; the middle cell of a three-cell run participates in two pairs.
- Is `colors` an input array? No; it is the evolving state initialized to zeros for this call.
### C++ Interface
```cpp
class Solution {
public:
vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
}
};
```
### Reasoning Checkpoints
- Preserve state across queries within one call.
- Distinguish an uncolored entry from a positive color.
- Include boundary positions and assignments that leave a color unchanged.
```hint A local change
Which adjacent pairs can possibly change when only one array position is recolored?
```
Overview: Apply a sequence of recoloring queries to an initially uncolored array. After each assignment, count adjacent positions with the same positive color, including overlapping pairs and repeated assignments while excluding uncolored neighbors.
