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 distinct colors among the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after the ith query.

Note: When answering a query, lack of a color will not be considered as a color.

Intuition

To solve this problem, we need to efficiently keep track of the colors assigned to each ball and determine the number of distinct colors after each query.

The solution involves using two hash tables:

1. Color Assignment Table (g): This tracks the current color assigned to each ball. For every query [x, y], we update the color of ball x to y.

2. Color Count Table (cnt): This keeps a count of how many balls currently use each color. Every time we change a ball's color, we update the count of the old and new colors. If a color's count becomes zero, we remove it, thereby ensuring we only track colors currently used.

After applying a query, the number of distinct colors is simply the size of the color count table (cnt), which is appended to the result list.

By maintaining these two tables, we efficiently manage color assignments and quickly compute the number of distinct colors as required.

Solution Approach

The solution utilizes a double hash table approach to keep track of the ball color assignments and the number of distinct colors.

1. Color Assignment Table (g): This dictionary records the current color of each ball. When we receive a query [x, y], it tells us what color to assign to the ball x.

2. Color Count Table (cnt): This utilizes a Counter, from the collections module in Python, to keep track of how many balls have a specific color. This helps in quickly assessing the number of distinct colors at any point.

Steps:

• Initialize an empty dictionary g to store current color assignments for each ball.
• Utilize a Counter called cnt to count occurrences of each color.
• Initialize an empty list ans to store the results after each query.

For each query [x, y]:

1. Increment the count of color y in cnt by one.
2. If ball x was previously colored (exists in g), reduce the count of its old color in cnt. If the decremented count drops to zero, remove that color from cnt.
3. Update the color of ball x to y in the g dictionary.
4. Append the current number of distinct colors, which is the size of cnt, to the result list ans.

Finally, return the list ans, containing the number of distinct colors after each query.

The solution effectively combines efficient data structures to update and track color data dynamically, enabling quick access to the required information after each query.

Example Walkthrough

Let's go through an example to demonstrate the solution approach.

Input:

• limit = 4
• queries = [[0, 1], [2, 2], [0, 2], [3, 1]]

The goal is to determine the number of distinct colors on the balls after each query.

Initial Setup:

• Color Assignment Table (g): An empty dictionary to track the color of each ball.
• Color Count Table (cnt): A Counter to keep count of how many balls are using each color.
• Result List (ans): An empty list to store the number of distinct colors after each query.

Process Queries:

1. Query [0, 1]:

   • Color ball 0 with color 1.
   • Update cnt: Increment color 1 by 1. Now, cnt is {1: 1}.
   • Record that ball 0 has color 1 in g: g = {0: 1}.
   • There is 1 distinct color, so append 1 to ans: ans = [1].

2. Query [2, 2]:

   • Color ball 2 with color 2.
   • Update cnt: Increment color 2 by 1. Now, cnt is {1: 1, 2: 1}.
   • Record that ball 2 has color 2 in g: g = {0: 1, 2: 2}.
   • There are 2 distinct colors, so append 2 to ans: ans = [1, 2].

3. Query [0, 2]:

   • Change ball 0's color from 1 to 2.
   • Update cnt:
     • Reduce count of color 1 by 1. Since count becomes zero, remove it: cnt = {2: 1}.
     • Increment count of color 2 by 1. cnt becomes {2: 2}.
   • Update g to reflect ball 0's new color: g = {0: 2, 2: 2}.
   • Still only 1 distinct color, so append 1 to ans: ans = [1, 2, 1].

4. Query [3, 1]:

   • Color ball 3 with color 1.
   • Update cnt: Increment color 1 by 1. Now, cnt is {2: 2, 1: 1}.
   • Record that ball 3 has color 1 in g: g = {0: 2, 2: 2, 3: 1}.
   • There are 2 distinct colors, so append 2 to ans: ans = [1, 2, 1, 2].

Final Result:

• The ans array, representing the number of distinct colors after each query, is [1, 2, 1, 2].

This walkthrough encapsulates the step-by-step process, utilizing hash tables to efficiently maintain and count colors on the balls.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(m), where m is the length of the array queries. This is because the code iterates through each query exactly once, and each operation inside the loop (such as updating the cnt counter or the dictionary g) is done in constant time.

The space complexity is also O(m), as the space used by the dictionary g and cnt counter is proportional to the number of queries, with each new entry being based on the elements within queries.

Learn more about how to find time and space complexity quickly.