Find the Number of Distinct Colors Among the Balls
MedPrompt
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 colors among the balls.
Return an array result of length n, where result[i] denotes the number of 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:
- After query 0, ball 1 has color 4.
- After query 1, ball 1 has color 4, and ball 2 has color 5.
- After query 2, ball 1 has color 3, and ball 2 has color 5.
- After query 3, ball 1 has color 3, ball 2 has color 5, and ball 3 has color 4.
Example 2:
Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Explanation:
- After query 0, ball 0 has color 1.
- After query 1, ball 0 has color 1, and ball 1 has color 2.
- After query 2, ball 0 has color 1, and balls 1 and 2 have color 2.
- After query 3, ball 0 has color 1, balls 1 and 2 have color 2, and ball 3 has color 4.
- After query 4, ball 0 has color 1, balls 1 and 2 have color 2, ball 3 has color 4, and ball 4 has color 5.
Constraints:
1 <= limit <= 1091 <= n == queries.length <= 105queries[i].length == 20 <= queries[i][0] <= limit1 <= queries[i][1] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach processes each query one by one. After each query, it determines the current color of every ball that has been mentioned so far and then counts the number of unique colors among them. This is straightforward but inefficient as it re-evaluates the state of the system repeatedly.
Algorithm
- Initialize an empty
HashMapcalledballToColorto store the mapping from a ball's label to its color. - Initialize an integer array
resultof the same size asqueries. - Iterate through the
queriesarray fromi = 0ton-1:- For the current query
[ball, color], update the map:ballToColor.put(ball, color). - Create a new
HashSetfrom the values of theballToColormap. - The size of this
HashSetis the number of distinct colors. - Store this size in
result[i].
- For the current query
- After the loop, return the
resultarray.
Walkthrough
We maintain a map, ballToColor, to store the current color of each ball. For each query, we update this map. After the update, we find the number of distinct colors by iterating through all the values (colors) in the ballToColor map and adding them to a HashSet. The size of the HashSet gives us the number of distinct colors. This process is repeated for every single query. The main drawback is the recalculation of distinct colors from scratch in every step, which involves iterating over all currently colored balls.
class Solution { public int[] getNumberOfDistinctColors(int limit, int[][] queries) { int n = queries.length; int[] result = new int[n]; Map<Integer, Integer> ballToColor = new HashMap<>(); for (int i = 0; i < n; i++) { int ball = queries[i][0]; int color = queries[i][1]; // Update the color of the ball ballToColor.put(ball, color); // Recalculate the number of distinct colors Set<Integer> distinctColors = new HashSet<>(ballToColor.values()); result[i] = distinctColors.size(); } return result; }}Complexity
Time
O(n^2), where n is the number of queries. For each of the n queries, we update a map (O(1)) and then iterate through all its current values to count distinct colors. The map can grow up to size `i` at step `i`. The total time is the sum of `i` from 1 to `n`, which is `1 + 2 + ... + n-1 = O(n^2)`.
Space
O(n), where n is the number of queries. The `ballToColor` map can store up to `n` entries if all queries are for distinct balls. The `HashSet` used for counting also takes up to O(n) space in the worst case.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem.
Cons
Inefficient for large inputs, likely resulting in a 'Time Limit Exceeded' error.
Performs a lot of redundant work by recounting all colors in every step.
Solutions
Solution
class Solution {public int[] queryResults(int limit, int[][] queries) { Map<Integer, Integer> g = new HashMap<>(); Map<Integer, Integer> cnt = new HashMap<>(); int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int x = queries[i][0], y = queries[i][1]; cnt.merge(y, 1, Integer : : sum); if (g.containsKey(x) && cnt.merge(g.get(x), -1, Integer : : sum) == 0) { cnt.remove(g.get(x)); } g.put(x, y); ans[i] = cnt.size(); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.