Find the Number of Distinct Colors Among the Balls - Video Solutions

Problem Overview: You receive queries that assign a color to a specific ball. After each assignment, you must report how many distinct colors currently exist among all colored balls. Balls may change colors multiple times, so the solution must correctly update color counts as assignments overwrite previous ones.

Approach 1: HashMap to Track Ball and Color Frequency (O(n) time, O(n) space)

Use two hash maps. The first maps ball -> color, storing the current color of each ball. The second maps color -> frequency, tracking how many balls currently use that color. For every query, check if the ball already has a color. If it does, decrement the frequency of the old color and remove it from the map when the count reaches zero. Then assign the new color, increment its frequency, and record the number of distinct colors as colorFrequency.size(). Each operation is constant time because hash lookups, insertions, and deletions are O(1) on average. This approach handles arbitrary ball IDs and color values efficiently and is the standard solution using Hash Table techniques combined with simple Simulation.

Approach 2: Arrays for Color Frequency (O(n) time, O(k) space)

If the maximum color value is reasonably bounded, replace the color-frequency hash map with an array. Maintain an array colorCount[color] that tracks how many balls currently have that color. You still keep a structure mapping ball -> color to detect previous assignments. When processing a query, decrement the previous color count, update the new color count, and maintain a running integer storing the number of distinct colors. Increment it when a color count transitions from 0 to 1, and decrement it when a count drops from 1 to 0. Array indexing is slightly faster than hashing and reduces overhead, making this a good optimization when color limits are known. The algorithm still processes each query once, so the total time remains O(n). This approach relies on simple operations over Array structures.

Recommended for interviews: The HashMap approach is what most interviewers expect. It works for large or sparse color ranges and demonstrates proper handling of state updates and frequency tracking. The array optimization is useful when constraints guarantee small color values, but the hash-based solution shows stronger general problem-solving skills.