Problem Description

You have limit + 1 balls labeled from 0 to limit. Initially, all balls are uncolored.

You're given a 2D array queries where each query is of the form [x, y]. For each query:

• Ball x gets marked with color y
• If ball x was already colored, its old color is replaced with the new color y

After processing each query, you need to count how many distinct colors are currently being used across all balls.

Your task is to return an array result where result[i] represents the number of distinct colors in use after processing the first i+1 queries.

Key Points:

• Balls can be recolored (their color gets replaced, not added)
• Uncolored balls don't count as having a color
• You need to track the number of unique colors after each query, not the number of colored balls

Example walkthrough: If you have queries [[0, 1], [1, 2], [0, 2]]:

• After query 1: Ball 0 has color 1 → 1 distinct color
• After query 2: Ball 0 has color 1, Ball 1 has color 2 → 2 distinct colors
• After query 3: Ball 0 changes to color 2, Ball 1 has color 2 → 1 distinct color

The result would be [1, 2, 1].

Intuition

The key insight is that we need to track two things simultaneously: which color each ball currently has, and how many balls have each color.

Think about what happens when we color a ball:

1. If the ball is being colored for the first time, we're adding a new ball to that color group
2. If the ball already had a color, we're removing it from its old color group and adding it to the new color group

This suggests we need two data structures:

• A mapping from ball → color (to know what color each ball currently has)
• A mapping from color → count (to know how many balls have each color)

The critical observation is that when a ball changes color, the count for its old color decreases by 1. If that count reaches 0, that color is no longer in use and should be removed from our tracking.

For example, if ball 0 has color 1 and we recolor it to color 2:

• Color 1's count decreases by 1
• Color 2's count increases by 1
• If color 1's count becomes 0, color 1 is no longer active

The number of distinct colors at any point is simply the number of colors that have a count greater than 0, which equals the size of our color-count mapping after removing colors with zero count.

This approach efficiently handles both adding new colors and removing colors that are no longer in use, giving us the exact count of distinct colors after each query in O(1) time per query.

Solution Approach

We implement the solution using two hash tables as identified in our intuition:

1. Hash table g: Maps each ball to its current color (ball → color)
2. Hash table cnt: Tracks the count of balls for each color (color → count)

Step-by-step implementation:

For each query [x, y] in queries:

1. Increment the count for the new color:

   • cnt[y] += 1 - This increases the count for color y by 1

2. Handle the ball's previous color (if any):

   • Check if ball x was already colored: if x in g
   • If yes, decrease the count of its old color: cnt[g[x]] -= 1
   • If the old color's count drops to 0, remove it from cnt:

     if cnt[g[x]] == 0:
         cnt.pop(g[x])

   • This ensures we only track colors that are actively in use

3. Update the ball's color:

   • g[x] = y - Record that ball x now has color y

4. Record the number of distinct colors:

   • ans.append(len(cnt)) - The size of cnt gives us the number of distinct colors currently in use

Why this works:

• The cnt hash table only contains colors with positive counts
• When a color's count reaches 0, we immediately remove it
• Therefore, len(cnt) always gives us the exact number of distinct colors

Time Complexity: O(n) where n is the number of queries, as each query is processed in O(1) time Space Complexity: O(min(n, limit)) for storing the ball-color mappings and color counts

Example Walkthrough

Let's trace through a small example with limit = 3 and queries [[1, 3], [2, 3], [1, 4], [2, 4]].

Initial State:

• g = {} (tracks which color each ball has)
• cnt = {} (tracks how many balls have each color)
• ans = [] (stores results)

Query 1: [1, 3] - Color ball 1 with color 3

1. Increment count for color 3: cnt[3] = 1 → cnt = {3: 1}
2. Ball 1 has no previous color (not in g), so skip the removal step
3. Update ball 1's color: g[1] = 3 → g = {1: 3}
4. Number of distinct colors = len(cnt) = 1
5. ans = [1]

Query 2: [2, 3] - Color ball 2 with color 3

1. Increment count for color 3: cnt[3] = 2 → cnt = {3: 2}
2. Ball 2 has no previous color (not in g), so skip the removal step
3. Update ball 2's color: g[2] = 3 → g = {1: 3, 2: 3}
4. Number of distinct colors = len(cnt) = 1
5. ans = [1, 1]

Query 3: [1, 4] - Recolor ball 1 from color 3 to color 4

1. Increment count for color 4: cnt[4] = 1 → cnt = {3: 2, 4: 1}
2. Ball 1 has previous color 3:
   • Decrease count: cnt[3] = 1 → cnt = {3: 1, 4: 1}
   • Count is not 0, so keep color 3 in cnt
3. Update ball 1's color: g[1] = 4 → g = {1: 4, 2: 3}
4. Number of distinct colors = len(cnt) = 2
5. ans = [1, 1, 2]

Query 4: [2, 4] - Recolor ball 2 from color 3 to color 4

1. Increment count for color 4: cnt[4] = 2 → cnt = {3: 1, 4: 2}
2. Ball 2 has previous color 3:
   • Decrease count: cnt[3] = 0 → cnt = {3: 0, 4: 2}
   • Count is 0, so remove color 3: cnt = {4: 2}
3. Update ball 2's color: g[2] = 4 → g = {1: 4, 2: 4}
4. Number of distinct colors = len(cnt) = 1
5. ans = [1, 1, 2, 1]

Final Result: [1, 1, 2, 1]

The key insight demonstrated here is how color 3 gets removed from tracking when its count drops to 0 (Query 4), ensuring we accurately count only the colors that are actively in use.

Solution Implementation

Time and Space Complexity

The time complexity is O(m), where m is the length of the array queries. Each query involves:

• Dictionary operations (g[x] lookup, assignment) which are O(1) on average
• Counter operations (cnt[y] += 1, cnt[g[x]] -= 1, cnt.pop()) which are O(1) on average
• Getting the length of the Counter with len(cnt) which is O(1)
• Appending to the answer list which is O(1)

Since we perform constant time operations for each of the m queries, the overall time complexity is O(m).

The space complexity is O(m), where m is the length of the array queries. This is because:

• Dictionary g can store at most m key-value pairs (one for each unique ball number in the queries)
• Counter cnt can store at most m entries (one for each unique color in the queries)
• List ans stores exactly m results (one for each query)

In the worst case, all queries could have unique ball numbers and unique colors, leading to space usage proportional to m.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Handle Color Replacement

Issue: A common mistake is treating each query as simply adding a new color to a ball, without properly handling the case where the ball already had a different color. This leads to overcounting distinct colors.

Incorrect approach:

def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
    ball_to_color = {}
    color_count = Counter()
    result = []
  
    for ball_number, new_color in queries:
        # Wrong: Just adding the new color without removing the old one
        ball_to_color[ball_number] = new_color
        color_count[new_color] += 1
        result.append(len(color_count))
  
    return result

Why it fails: If ball 0 changes from color 1 to color 2, this approach would count both colors as being in use, even though color 1 is no longer present on any ball.

Solution: Always check if the ball had a previous color and properly decrement its count:

if ball_number in ball_to_color:
    old_color = ball_to_color[ball_number]
    color_count[old_color] -= 1
    if color_count[old_color] == 0:
        color_count.pop(old_color)

Pitfall 2: Not Removing Colors with Zero Count

Issue: Keeping colors with zero count in the counter leads to incorrect distinct color counts.

Incorrect approach:

if ball_number in ball_to_color:
    old_color = ball_to_color[ball_number]
    color_count[old_color] -= 1
    # Forgot to remove the color when count reaches 0!

Why it fails: len(color_count) would include colors that aren't actually on any balls, giving inflated results.

Solution: Always remove colors from the counter when their count reaches zero:

if color_count[old_color] == 0:
    color_count.pop(old_color)

Pitfall 3: Order of Operations Error

Issue: Updating the ball's color mapping before handling the old color removal.

Incorrect approach:

for ball_number, new_color in queries:
    # Wrong: Updating ball color first
    old_color = ball_to_color.get(ball_number)
    ball_to_color[ball_number] = new_color  # This overwrites the old color!
  
    if old_color is not None:
        color_count[old_color] -= 1
        # ...rest of logic

Why it fails: While this particular version might work if you save the old color first, it's error-prone and can lead to confusion or bugs if the code is modified later.

Solution: Follow a clear sequence:

1. First, increment the new color count
2. Then, handle the old color (if exists)
3. Finally, update the ball's color mapping

This ensures the logic flow is clear and maintainable.