#3160

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Number of Distinct Colors Among the Balls

Efficiently track colors on balls using array scanning and hash lookup to return the count of distinct colors after each update query.

array hash table simulation

Problem Statement

You have a set of balls labeled from 0 to limit, all initially uncolored. You are given a list of queries, each represented as [x, y], where you color ball x with color y. After each query, determine how many distinct colors are present among all the balls.

Return an array result where result[i] is the number of distinct colors after processing the ith query. Use efficient array scanning with hash-based tracking to handle up to 10^5 queries without redundant full-array checks.

Examples

Example 1

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

Output: [1,2,2,3]

Example 2

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

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

Constraints

1 <= limit <= 109
1 <= n == queries.length <= 105
queries[i].length == 2
0 <= queries[i][0] <= limit
1 <= queries[i][1] <= 109

Solution Approach

Use HashMap to Track Ball Colors

Maintain a HashMap mapping each ball to its current color. For every query [x, y], update the color of ball x. This ensures quick lookup and update of individual balls without scanning all balls each time.

Maintain Color-to-Ball Sets

Keep a second HashMap that maps each color to a set of balls currently having that color. After each query, update this map by removing the ball from its previous color set and adding it to the new color set. The number of keys in this map gives the distinct color count.

Process Queries Efficiently

Iterate through all queries, updating both maps as described. After each update, append the current count of distinct colors to the result array. This leverages array scanning plus hash lookup to achieve O(n) time without redundant checks.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each query triggers a constant-time hash map update. Space complexity is O(n) due to storing ball-to-color and color-to-ball maps for all balls and queries.

What Interviewers Usually Probe

Do you track the previous color when updating a ball to avoid double counting?
Can you maintain a reverse map from colors to sets of balls for constant-time distinct count?
How would your solution scale if the limit of balls is very large compared to the number of queries?

Common Pitfalls or Variants

Common pitfalls

Failing to remove a ball from its previous color set leads to overcounting distinct colors.
Iterating over all balls after each query instead of using hash maps causes timeouts on large n.
Using only a ball-to-color map without a reverse color-to-ball map prevents efficient distinct color counting.

Follow-up variants

Count distinct colors only within a specified range of balls for each query.
Allow recoloring multiple balls at once in a single query and compute distinct colors after batch updates.
Track not only distinct color counts but also the most frequent color after each query.

FAQ

What pattern does 'Find the Number of Distinct Colors Among the Balls' rely on?

It uses array scanning combined with hash lookup, tracking both ball colors and reverse color sets to count distinct colors efficiently.

Can this approach handle the maximum constraints?

Yes, using hash maps for O(1) updates per query allows handling up to 10^5 queries with limits up to 10^9.

What is a common mistake when counting distinct colors?

Not updating the reverse color-to-ball map correctly leads to double-counting or missing colors after recoloring.

Is it necessary to iterate over all balls after each query?

No, hash-based tracking eliminates the need for full-array scans, providing constant-time distinct color count retrieval.

How do I modify this solution for range queries?

You can maintain separate structures for ranges, such as segment trees with color sets, to compute distinct colors over subarrays efficiently.

terminal

Solution

Solution 1: Double Hash Tables

We use a hash table `g` to record the color of each ball, and another hash table `cnt` to record the count of each color.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        g = {}
        cnt = Counter()
        ans = []
        for x, y in queries:
            cnt[y] += 1
            if x in g:
                cnt[g[x]] -= 1
                if cnt[g[x]] == 0:
                    cnt.pop(g[x])
            g[x] = y
            ans.append(len(cnt))
        return ans

Continue Practicing

#3080 mark elements on array by performing queries #3242 design neighbor sum service #3507 minimum pair removal to sort array i