Number of Adjacent Elements With the Same Color

Number of Adjacent Elements With the Same Color - Problem

Array Medium

You are given an integer n representing an array colors of length n where all elements are initially set to 0 (uncolored).

You are also given a 2D integer array queries where queries[i] = [index_i, color_i].

For each query:

Set colors[index_i] to color_i
Count the number of adjacent pairs in the array that have the same color

Return an array answer where answer[i] is the count of same-colored adjacent pairs after the i-th query.

Input & Output

Example 1 — Basic Color Updates

$ Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

› Output: [0,1,1,0,2]

💡 Note: Initially [0,0,0,0]. After [0,2]: [2,0,0,0] → 0 pairs. After [1,2]: [2,2,0,0] → 1 pair (2,2). After [3,1]: [2,2,0,1] → 1 pair. After [1,1]: [2,1,0,1] → 0 pairs. After [2,1]: [2,1,1,1] → 2 pairs.

Example 2 — Single Element

$ Input: n = 1, queries = [[0,1]]

› Output: [0]

💡 Note: Array [1] has no adjacent pairs, so count is 0.

Example 3 — No Adjacent Matches

$ Input: n = 3, queries = [[0,1],[1,2],[2,3]]

› Output: [0,0,0]

💡 Note: Array becomes [1,2,3] with no adjacent elements having the same color.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
queries[i].length == 2
0 ≤ index_i < n
1 ≤ color_i ≤ 10⁵

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that we only need to check adjacent pairs involving the updated position. The optimized approach maintains a running count and updates it in O(1) per query. Time: O(q), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Recount Everything	O(q × n)	O(1)	After each query, scan the entire array to count adjacent same-colored pairs
Smart Update - Track Changes	O(q)	O(1)	Only check the updated position's neighbors to efficiently update the count

Brute Force - Recount Everything — Algorithm Steps

Process each query by updating the color
Scan entire array counting adjacent same-colored pairs
Store the count in result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Update Color

Set colors[index] = color

Scan Array

Count all adjacent same-color pairs

Store Count

Add count to result array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int n, int** queries, int queriesSize, int* returnSize) {
    int* colors = (int*)calloc(n, sizeof(int));
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int index = queries[q][0];
        int color = queries[q][1];
        colors[index] = color;
        
        // Count adjacent pairs with same color
        int count = 0;
        for (int i = 0; i < n - 1; i++) {
            if (colors[i] != 0 && colors[i] == colors[i + 1]) {
                count++;
            }
        }
        
        result[q] = count;
    }
    
    free(colors);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for small inputs
    int queries[1000][2];
    int queriesSize = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            queries[queriesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            queries[queriesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            queriesSize++;
        } else {
            ptr++;
        }
    }
    
    int* queryPtrs[1000];
    for (int i = 0; i < queriesSize; i++) {
        queryPtrs[i] = queries[i];
    }
    
    int returnSize;
    int* result = solution(n, queryPtrs, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

q queries, each requiring O(n) scan of the array

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, result array doesn't count toward space

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Recount Everything — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler