Problem Description
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 the i-th query.
Key Insights
- Each ball can only have one color at a time.
- The number of distinct colors is determined by the unique colors assigned to the balls.
- A hash table (or dictionary) can be used to track the current color of each ball.
- The number of distinct colors can be efficiently maintained by using a set or by counting unique values in the hash table after each query.
Space and Time Complexity
Time Complexity: O(n) for processing all queries, where n is the number of queries. Each query takes O(1) on average for inserting and checking colors in a hash table.
Space Complexity: O(m) where m is the number of distinct colors used. In the worst case, it could be O(n) if all balls are colored with different colors.
Solution
The algorithm uses a hash table (dictionary) to keep track of the color assigned to each ball. For each query, we update the color of the specified ball. We then maintain a set to track the distinct colors that are currently assigned. After processing each query, we record the size of this set, which represents the number of distinct colors.