Number of Adjacent Elements With the Same Color

Medium
1839.

Number of Adjacent Elements With the Same Color

Number of Adjacent Elements With the Same Color is a medium coding problem on arrays and simulation, asked in Amazon and Google interviews.

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^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= index <= n - 1
  • 1 <= color <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number[]}
 */
var colorTheArray = function(n, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= index <= n - 1
  • 1 <= color <= 10^5

Hints for Number of Adjacent Elements With the Same Color

  1. Hint 1

    Recounting every pair after each query is O(n) per query — too slow for 10^5 queries. Only the pairs that touch the painted cell can change.

  2. Hint 2

    Keep a running count. A query at index only affects the pairs (index - 1, index) and (index, index + 1).

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

  1. Keep the colours in an array of zeros and a counter count = 0.
  2. For a query [i, c], if cell i is coloured, subtract one for each neighbour (i - 1, i + 1) that exists and holds the same colour as cell i.
  3. Paint cell i with c.
  4. Add one for each existing neighbour that now holds c, and record count.

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 with old != 0 (the addition is safe because color >= 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 answer

Java

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