MEDIUM
3160. Find the Number of Distinct Colors Among the Balls
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 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 colors after the i-th query.
Example
Example 1:
Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Example 2:
Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]
Output: [1,2,2,3,4]
Constraints
- 1 <= limit <= 10⁹
- 1 <= n == queries.length <= 10⁵
- queries[i].length == 2
- 0 <= queries[i][0] <= limit
- 1 <= queries[i][1] <= 10⁹
Solution: Hash Table + Simulation
- Time Complexity: O(n), where n is the number of queries.
- Space Complexity: O(n), for storing ball colors and color counts.
C++
class Solution {
public:
vector<int> queryResults(int limit, vector<vector<int>>& queries) {
unordered_map<int, int> ballColor; // ball -> color
unordered_map<int, int> colorCount; // color -> count of balls
vector<int> res;
for (auto& q : queries) {
int ball = q[0], color = q[1];
if (ballColor.count(ball)) {
int prevColor = ballColor[ball];
colorCount[prevColor]--;
if (colorCount[prevColor] == 0) colorCount.erase(prevColor);
}
ballColor[ball] = color;
colorCount[color]++;
res.push_back(colorCount.size());
}
return res;
}
};