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 the balls.
Return an array result of length n, where result[i] denotes the number of distinct colors after ith query.
Note that when answering a query, lack of a color will not be considered as a color.
Example 1:
Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Explanation:
Example 2:
Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Explanation:
Constraints:
1 <= limit <= 1091 <= n == queries.length <= 105queries[i].length == 20 <= queries[i][0] <= limit1 <= queries[i][1] <= 109Problem 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.
This approach uses a HashMap (or Dictionary in Python) to map each ball to its current color. By iterating over the queries, you update the color of each specified ball in the map. To determine the distinct colors, you can utilize a HashSet (or Set in Python) which keeps track of all unique values in the HashMap.
In this solution, we maintain an array to keep track of the color of each ball and an array to track which colors are present and how often they occur. After each query, we check if the new color increments the count of distinct colors or remove a previous color, and then we store the count in the result array. Finally, we output the results.
Time Complexity: O(n), where n is the number of queries, because we are processing each query in constant time.
Space Complexity: O(m), where m is the limit plus one for the ball array.
This approach leverages arrays to keep track of the last-assigned color for each ball and the frequency of each color used. By maintaining these two structures, we can efficiently query the number of distinct colors active at any moment.
This C solution uses two arrays; one tracking the color assigned to each ball, and another keeping the frequency of each color. By updating these arrays on each query, it efficiently computes the number of distinct colors at any given point.
Time Complexity: O(n), where n is the number of queries, as each query requires constant time operation on arrays.
Space Complexity: O(m + k), where m is the number of balls handled and k is manageable maximum distinct colors.
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.
Next, we traverse the array queries. For each query (x, y), we increase the count of color y by 1, then check whether ball x has been colored. If it has, we decrease the count of the color of ball x by 1. If the count drops to 0, we remove it from the hash table cnt. Then, we update the color of ball x to y, and add the current size of the hash table cnt to the answer array.
After the traversal, we return the answer array.
The time complexity is O(m), and the space complexity is O(m), where m is the length of the array queries.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using a HashMap or Dictionary to Track Colors | Time Complexity: O(n), where n is the number of queries, because we are processing each query in constant time. Space Complexity: O(m), where m is the limit plus one for the ball array. |
| Using Arrays for Color Frequency | Time Complexity: O(n), where n is the number of queries, as each query requires constant time operation on arrays. Space Complexity: O(m + k), where m is the number of balls handled and k is manageable maximum distinct colors. |
| Double Hash Tables | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap for Ball Color + Color Frequency | O(n) | O(n) | General case when ball IDs and colors may be large or sparse |
| Array for Color Frequency | O(n) | O(k) | When color values are bounded and an array is more memory‑efficient |
Find the Number of Distinct Colors Among the Balls | 2 Approaches | Leetcode 3160 | codestorywithMIK • codestorywithMIK • 8,863 views views
Watch 9 more video solutions →Practice Find the Number of Distinct Colors Among the Balls with our built-in code editor and test cases.
Practice on FleetCode