Maintain the number of distinct colors after a sequence of ball recoloring operations.
You are given balls labeled from $1n$, and each ball initially has no color. You then receive a list of queries, where each query recolors one ball with a given color.
After every recoloring operation, report how many distinct colors are currently present among all balls.
If a ball is recolored, its previous color is replaced by the new one. Balls with no assigned color are ignored when counting distinct colors.
Input Format
Input
- An integer representing the number of balls.
- A list of queries, where each query is an ordered pair
([ball, color])meaning ballballis recolored tocolor.
Interpretation
- Ball indices are 1-based.
- A ball can be recolored multiple times.
- Color values may repeat across different balls.
Output Format
Output
- Return an array where the -th value is the number of distinct colors present after processing the -th query.
Constraints
- number of queries
- Ball indices are valid
- Color values fit in a standard 32-bit integer
- Aim for near-linear total time
Example 1
Input
n = 4 queries = [[1, 5], [2, 5], [1, 3], [4, 2]]
Output
[1, 1, 2, 3]
Explanation
After each query, the distinct color sets are:
- {5}
- {5}
- {5, 3}
- {5, 3, 2}
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.