Number of Adjacent Elements With the Same Color — Solution
Number of Adjacent Elements With the Same Color solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Adjacent Elements With the Same Color is a medium coding problem on arrays and simulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A row of n cells starts out uncoloured — every cell holds 0. You then process queries in order, where queries[i] = [index, color] paints cell index with color (overwriting whatever it held; color is always at least 1).
After each query, count the pairs of neighbouring cells j and j + 1 that are both coloured and hold the same colour. Uncoloured cells never form a pair.
Return an array whose i-th entry is that count right after 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: The row goes [2,0,0,0] → [2,2,0,0] → [2,2,0,1] → [2,1,0,1] → [2,1,1,1]; the last row has the pairs (1,2) and (2,3).
Example 2
Input: n = 3, queries = [[1,5],[1,5],[0,5],[2,5],[1,3]]
Output: [0,0,1,2,0]
Explanation: Repainting a cell with its own colour changes nothing; painting the middle cell 3 breaks both pairs at once.
Example 3
Input: n = 1, queries = [[0,100000]]
Output: [0]
Explanation: A single cell has no neighbour.
Constraints
1 <= n <= 10^51 <= queries.length <= 10^5queries[i].length == 20 <= index <= n - 11 <= color <= 10^5
Hints for Number of Adjacent Elements With the Same Color
Hint 1
Recounting every pair after each query is
O(n)per query — too slow for10^5queries. Only the pairs that touch the painted cell can change.Hint 2
Keep a running count. A query at
indexonly affects the pairs(index - 1, index)and(index, index + 1).Hint 3
Before repainting, subtract the pairs the cell's old colour formed with its neighbours (only if it was coloured); after repainting, add the pairs the new colour forms.
How to solve Number of Adjacent Elements With the Same Color
A query changes one cell, and a cell belongs to at most two neighbouring pairs, so the number of equal pairs can be maintained incrementally in O(1) per query.
Approach
- Keep the colours in an array of zeros and a counter
count = 0. - For a query
[i, c], if celliis coloured, subtract one for each neighbour (i - 1,i + 1) that exists and holds the same colour as celli. - Paint cell
iwithc. - Add one for each existing neighbour that now holds
c, and recordcount.
Why it works
Every pair not containing cell i is untouched by the query, so its contribution to the count is unchanged. The two pairs that do contain i are first removed with their old status and then re-added with their new one, so after each query count equals the true number of equal coloured pairs.
Complexity
- Time —
O(n + q) - Space —
O(n)
Pitfalls
- An uncoloured cell (
0) must never pair with another uncoloured cell — guard the subtraction withold != 0(the addition is safe becausecolor >= 1). - Repainting a cell with the colour it already has must leave the count unchanged; subtract-then-add handles it naturally.
- Check the array bounds for both neighbours, especially when
n = 1.
Reference solution
Python
from typing import List
def colorTheArray(n: int, queries: List[List[int]]) -> List[int]:
colors = [0] * n
count = 0
answer = []
for i, c in queries:
old = colors[i]
if old != 0:
if i > 0 and colors[i - 1] == old:
count -= 1
if i + 1 < n and colors[i + 1] == old:
count -= 1
colors[i] = c
if i > 0 and colors[i - 1] == c:
count += 1
if i + 1 < n and colors[i + 1] == c:
count += 1
answer.append(count)
return answerJava
public static int[] colorTheArray(int n, int[][] queries) {
int[] colors = new int[n];
int[] answer = new int[queries.length];
int count = 0;
for (int q = 0; q < queries.length; q++) {
int i = queries[q][0], c = queries[q][1];
int old = colors[i];
if (old != 0) {
if (i > 0 && colors[i - 1] == old) count--;
if (i + 1 < n && colors[i + 1] == old) count--;
}
colors[i] = c;
if (i > 0 && colors[i - 1] == c) count++;
if (i + 1 < n && colors[i + 1] == c) count++;
answer[q] = count;
}
return answer;
}C++
vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
vector<int> colors(n, 0), answer;
int count = 0;
for (auto& qu : queries) {
int i = qu[0], c = qu[1];
int old = colors[i];
if (old != 0) {
if (i > 0 && colors[i - 1] == old) count--;
if (i + 1 < n && colors[i + 1] == old) count--;
}
colors[i] = c;
if (i > 0 && colors[i - 1] == c) count++;
if (i + 1 < n && colors[i + 1] == c) count++;
answer.push_back(count);
}
return answer;
}JavaScript
var colorTheArray = function(n, queries) {
var colors = new Array(n);
for (var k = 0; k < n; k++) colors[k] = 0;
var count = 0;
var answer = [];
for (var q = 0; q < queries.length; q++) {
var i = queries[q][0], c = queries[q][1];
var old = colors[i];
if (old !== 0) {
if (i > 0 && colors[i - 1] === old) count--;
if (i + 1 < n && colors[i + 1] === old) count--;
}
colors[i] = c;
if (i > 0 && colors[i - 1] === c) count++;
if (i + 1 < n && colors[i + 1] === c) count++;
answer.push(count);
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays