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] <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Find the Number of Distinct Colors Among the Balls | Leetcode 3160 • Techdose • 7,179 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