Find the Number of Distinct Colors Among the Balls

Find the Number of Distinct Colors Among the Balls

What is this problem about?

The Find the Number of Distinct Colors Among the Balls coding problem asks you to simulate coloring a series of balls. You are given a sequence of queries, where each query [ballIndex, color] tells you to paint a specific ball with a new color. If the ball was already colored, its previous color is replaced. After each query, you need to return the total number of distinct colors currently present across all colored balls.

Why is this asked in interviews?

Google and Amazon ask this to test your ability to maintain multiple state dependencies in real-time. It evaluation your proficiency with Hash Table design patterns. Specifically, you need to track which ball has which color and how many balls share each color. This ensures that when a color is replaced, you know if that color has completely disappeared from the set of balls.

Algorithmic pattern used

This problem uses Frequency Counting with two Hash Tables.

1. ballToColor: A map from ballIndex to its current color.
2. colorCount: A map from color to the number of balls that currently have that color.
3. For each query [ball, newColor]:
   • If the ball was already in ballToColor:
     • Decrement the count of its oldColor in colorCount.
     • If colorCount[oldColor] becomes 0, remove the color from the map.
   • Update ballToColor[ball] to newColor.
   • Increment the count of newColor in colorCount.
4. The number of distinct colors is the current size of the colorCount map.

Example explanation

Query 1: [1, 10] (Ball 1 gets color 10). ballToColor: {1: 10}, colorCount: {10: 1}. Distinct colors = 1. Query 2: [2, 10] (Ball 2 gets color 10). ballToColor: {1: 10, 2: 10}, colorCount: {10: 2}. Distinct colors = 1. Query 3: [1, 20] (Ball 1 changes to color 20).

• Old color 10 count becomes 1.
• New color 20 count becomes 1. Distinct colors = 2 (10 and 20).

Common mistakes candidates make

• Only tracking distinct colors: Forgetting that if two balls have the same color and one changes, the color might still be present on the other ball.
• Inefficient Search: Re-scanning all balls after every query to count colors ($O(Q imes N)$), which is too slow.
• Memory Management: Not removing colors from the count map when their frequency hits zero, leading to incorrect size reports.

Interview preparation tip

Whenever you need to track "Distinct elements in a dynamic set," you usually need two pieces of information: the current mapping and a frequency count of the values. This allows you to update the set's diversity in $O(1)$ time.