# Find the Number of Distinct Colors Among the Balls **Difficulty:** MEDIUM [External](https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls) Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-distinct-colors-among-the-balls **Data structures:** Array, Hash Table --- ## Problem 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:** ![](https://assets.glich.co/dsa/find-the-number-of-distinct-colors-among-the-balls/image0.gif) * 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:** **![](https://assets.glich.co/dsa/find-the-number-of-distinct-colors-among-the-balls/image1.gif)** * 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 <= 109` * `1 <= n == queries.length <= 105` * `queries[i].length == 2` * `0 <= queries[i][0] <= limit` * `1 <= queries[i][1] <= 109` # Approaches ## Brute Force by Recalculating After Each Query 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. **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. **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. ### Explanation 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. ```java class Solution { public int[] getNumberOfDistinctColors(int limit, int[][] queries) { int n = queries.length; int[] result = new int[n]; Map 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 distinctColors = new HashSet<>(ballToColor.values()); result[i] = distinctColors.size(); } return result; } } ``` ### Algorithm - Initialize an empty `HashMap` called `ballToColor` to store the mapping from a ball's label to its color. - Initialize an integer array `result` of the same size as `queries`. - Iterate through the `queries` array from `i = 0` to `n-1`: - For the current query `[ball, color]`, update the map: `ballToColor.put(ball, color)`. - Create a new `HashSet` from the values of the `ballToColor` map. - The size of this `HashSet` is the number of distinct colors. - Store this size in `result[i]`. - After the loop, return the `result` array. ## Efficient Approach using Two HashMaps This optimized approach avoids recalculation by maintaining the counts of each color in real-time. It uses two maps: one to track the color of each ball (`ballToColor`) and another to track how many balls have a certain color (`colorToCount`). This allows for O(1) updates per query, making it highly efficient. **Time:** O(n), where n is the number of queries. Each query involves a constant number of `HashMap` operations (get, put, remove), which take O(1) time on average. Therefore, the total time complexity is linear with respect to the number of queries. · **Space:** O(n), where n is the number of queries. In the worst-case scenario, each query could involve a new ball and a new color. This would mean both `ballToColor` and `colorToCount` maps could grow to a size of up to `n`. **Pros:** Highly efficient, with linear time complexity.; Scales well with large numbers of queries.; Optimal solution for the given constraints. **Cons:** Slightly more complex to implement than the brute-force approach due to the need to manage two maps and their state correctly. ### Explanation We use two `HashMap`s: 1. `ballToColor`: Maps a ball's label to its current color. 2. `colorToCount`: Maps a color to the number of balls currently painted with that color. When processing a query `[x, y]`: 1. Check if ball `x` already has a color by looking it up in `ballToColor`. 2. If it does (`oldColor`), we decrement the count of `oldColor` in `colorToCount`. If this count drops to zero, it means no ball has this color anymore, so we remove `oldColor` from `colorToCount`. 3. We then update ball `x`'s color to `y` in `ballToColor`. 4. We increment the count of the new color `y` in `colorToCount`. If `y` was not in `colorToCount` before, it's added with a count of 1. The number of distinct colors after each query is simply the size of the `colorToCount` map. This is because this map only holds entries for colors that are currently in use (i.e., have a count > 0). ```java class Solution { public int[] getNumberOfDistinctColors(int limit, int[][] queries) { int n = queries.length; int[] result = new int[n]; Map ballToColor = new HashMap<>(); Map colorToCount = new HashMap<>(); for (int i = 0; i < n; i++) { int ball = queries[i][0]; int newColor = queries[i][1]; // Check if the ball was already colored if (ballToColor.containsKey(ball)) { int oldColor = ballToColor.get(ball); // If the new color is the same as the old one, nothing changes if (oldColor == newColor) { result[i] = colorToCount.size(); continue; } // Decrement the count of the old color int oldCount = colorToCount.get(oldColor); if (oldCount == 1) { colorToCount.remove(oldColor); } else { colorToCount.put(oldColor, oldCount - 1); } } // Update the ball's color ballToColor.put(ball, newColor); // Increment the count of the new color colorToCount.put(newColor, colorToCount.getOrDefault(newColor, 0) + 1); // The number of distinct colors is the size of the colorToCount map result[i] = colorToCount.size(); } return result; } } ``` ### Algorithm - Initialize two empty `HashMap`s: `ballToColor` (ball -> color) and `colorToCount` (color -> count). - Initialize an integer array `result` of size `n`. - Iterate through the `queries` array from `i = 0` to `n-1`: - Let the current query be `[ball, newColor]`. - Check if `ball` exists as a key in `ballToColor`. - If it exists: - Get its `oldColor`. - If `oldColor` is the same as `newColor`, no change in distinct colors, so continue to the next query after recording the current count. - Decrement the count of `oldColor` in `colorToCount`. - If the count of `oldColor` becomes 0, remove it from `colorToCount`. - Update the ball's color in the `ballToColor` map: `ballToColor.put(ball, newColor)`. - Increment the count of `newColor` in `colorToCount` (using `getOrDefault` for convenience). - The number of distinct colors is `colorToCount.size()`. Store this in `result[i]`. - After the loop, return the `result` array. # Solutions ### Java ```java class Solution { public int[] queryResults(int limit, int[][] queries) { Map g = new HashMap<>(); Map 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; } } ``` ### CPP ```cpp class Solution { public: vector queryResults(int limit, vector> &queries) { unordered_map g; unordered_map cnt; vector ans; for (auto &q : queries) { int x = q[0], y = q[1]; cnt[y]++; if (g.contains(x) && --cnt[g[x]] == 0) { cnt.erase(g[x]); } g[x] = y; ans.push_back(cnt.size()); } return ans; } }; ``` ### Python ```python class Solution: def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]: g = {} cnt = Counter() ans = [] for x, y in queries: cnt[y] += 1 if x in g: cnt[g[x]] -= 1 if cnt[g[x]] == 0: cnt . pop(g[x]) g[x] = y ans . append(len(cnt)) return ans ```