Find the Number of Distinct Colors Among the Balls - Problem

You are given an integer limit and a 2D array queries of size n x 2.

There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored.

For every query in queries that is of the form [x, y], you mark ball x with the color y.

After each query, you need to find the number of distinct colors among all the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after the i-th query.

Note: When answering a query, lack of a color will not be considered as a color.

Input & Output

Example 1 — Basic Coloring

$ Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

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

💡 Note: Initially all balls uncolored. Query [1,4]: ball 1→color 4, distinct colors={4}→1. Query [2,5]: ball 2→color 5, distinct colors={4,5}→2. Query [1,3]: ball 1→color 3, distinct colors={3,5}→2. Query [3,4]: ball 3→color 4, distinct colors={3,4,5}→3.

Example 2 — Same Color Multiple Balls

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

› Output: [1,1,1]

💡 Note: All queries use same color 1. After each query: distinct colors={1}→1.

Example 3 — Recoloring Ball

$ Input: limit = 2, queries = [[0,1],[0,2],[1,1]]

› Output: [1,1,2]

💡 Note: Query [0,1]: ball 0→color 1, colors={1}→1. Query [0,2]: ball 0→color 2, colors={2}→1. Query [1,1]: ball 1→color 1, colors={1,2}→2.

Constraints

1 ≤ limit ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
queries[i].length == 2
0 ≤ queries[i][0] ≤ limit
1 ≤ queries[i][1] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to track distinct colors efficiently using a hash map instead of rescanning all balls. The optimized approach maintains a color count map, updating it in O(1) time per query. Time: O(n), Space: O(colors).

Common Approaches

✓ Sliding Window

⏱️ Time: N/A Space: N/A

Brute Force - Rescan After Each Query

⏱️ Time: O(n × limit) Space: O(limit)

For each query, update the ball's color, then iterate through all balls to count how many distinct colors exist. This approach recalculates everything from scratch after each update.

Optimized - Track Color Set

⏱️ Time: O(n) Space: O(limit + colors)

Maintain a set of colors that are currently used by balls. When a ball changes color, update the set accordingly. This avoids rescanning all balls after each query.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

static int ballColors[100001];  // ballColors[i] = color of ball i (0 = uncolored)
static int colorFreq[100001];   // colorFreq[i] = how many balls have color i

int* solution(int limit, int queries[][2], int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    
    // Initialize
    memset(ballColors, 0, sizeof(ballColors));
    memset(colorFreq, 0, sizeof(colorFreq));
    int distinctColors = 0;
    
    for (int i = 0; i < queriesSize; i++) {
        int ball = queries[i][0];
        int newColor = queries[i][1];
        
        // Remove old color if ball was colored
        if (ballColors[ball] != 0) {
            int oldColor = ballColors[ball];
            colorFreq[oldColor]--;
            if (colorFreq[oldColor] == 0) {
                distinctColors--;
            }
        }
        
        // Add new color
        ballColors[ball] = newColor;
        if (colorFreq[newColor] == 0) {
            distinctColors++;
        }
        colorFreq[newColor]++;
        
        result[i] = distinctColors;
    }
    
    return result;
}

int main() {
    int limit;
    scanf("%d", &limit);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);  // consume newline
    fgets(line, sizeof(line), stdin);  // read queries line
    
    static int queries[1000][2];
    int queriesSize = 0;
    
    // Parse queries [[1,4],[2,5],[1,3],[3,4]]
    char* p = line;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == '[') {
            p++;
            // Parse first number
            queries[queriesSize][0] = (int)strtol(p, &p, 10);
            while (*p == ' ' || *p == ',') p++;
            // Parse second number
            queries[queriesSize][1] = (int)strtol(p, &p, 10);
            queriesSize++;
            while (*p && *p != ']') p++;
            if (*p == ']') p++;
        } else {
            p++;
        }
    }
    
    int returnSize;
    int* result = solution(limit, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

245 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