Find the Number of Distinct Colors Among the Balls

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,2]

💡 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

Understanding the Visualization

Input

limit=4, queries=[[1,4],[2,5],[1,3]]

Process

Color balls and track distinct colors

Output

Array of distinct color counts: [1,2,2]

Key Takeaway

🎯 Key Insight: Use a hash map to track color counts efficiently, avoiding the need to rescan all balls after each query

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

Approach	Time	Space	Notes
✓ Brute Force - Rescan After Each Query	O(n × limit)	O(limit)	After each query, scan all balls to count distinct colors
Optimized - Track Color Set	O(n)	O(limit + colors)	Use a set to efficiently track distinct colors without rescanning

Brute Force - Rescan After Each Query — Algorithm Steps

Process each query by updating ball color
Scan all balls to find distinct colors
Count unique colors and store result

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Query

Update ball with new color

Scan All Balls

Check every ball to find colors

Count Distinct

Count unique colors found

Code -

solution.c — C

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

int* solution(int limit, int** queries, int queriesSize, int* returnSize) {
    int* balls = (int*)malloc((limit + 1) * sizeof(int));
    for (int i = 0; i <= limit; i++) {
        balls[i] = -1; // -1 means uncolored
    }
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int x = queries[i][0], y = queries[i][1];
        balls[x] = y;
        
        // Count distinct colors using a simple array
        int maxColor = 0;
        for (int j = 0; j <= limit; j++) {
            if (balls[j] != -1 && balls[j] > maxColor) {
                maxColor = balls[j];
            }
        }
        
        int* colorSeen = (int*)calloc(maxColor + 1, sizeof(int));
        int distinctCount = 0;
        
        for (int j = 0; j <= limit; j++) {
            if (balls[j] != -1 && !colorSeen[balls[j]]) {
                colorSeen[balls[j]] = 1;
                distinctCount++;
            }
        }
        
        result[i] = distinctCount;
        free(colorSeen);
    }
    
    free(balls);
    return result;
}

int main() {
    int limit;
    scanf("%d", &limit);
    
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for queries
    int queriesSize = 0;
    int** queries = (int**)malloc(1000 * sizeof(int*));
    
    char* token = strtok(line, "[],");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            if (queriesSize % 2 == 0) {
                queries[queriesSize / 2] = (int*)malloc(2 * sizeof(int));
                queries[queriesSize / 2][0] = atoi(token);
            } else {
                queries[queriesSize / 2][1] = atoi(token);
            }
            queriesSize++;
        }
        token = strtok(NULL, "[],");
    }
    queriesSize /= 2;
    
    int returnSize;
    int* result = solution(limit, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    for (int i = 0; i < queriesSize; i++) {
        free(queries[i]);
    }
    free(queries);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × limit)

For each of n queries, we scan up to limit+1 balls to count colors

✓ Linear Growth

Space Complexity

O(limit)

Array to store ball colors, plus set for counting distinct colors

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Rescan After Each Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler