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

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

Note that when answering a query, lack of a color will not be considered as a color.

Examples

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]
Output: [1,2,2,3]
Explanation:
* 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:
* 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 <= 10^9
  • 1 <= n == queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= queries[i][0] <= limit
  • 1 <= queries[i][1] <= 10^9

Solution

The key challenge is to efficiently track and manage the colors of the balls after each query. Each query specifies a ball and a color, and our goal is to determine the number of distinct colors present after processing each query.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

The naive approach is straightforward but inefficient. It involves updating the color of the specified ball for each query, followed by a linear scan of the entire list of balls to count the number of distinct colors.

Complexity

  • ⏰ Time complexity: O(n * m) , where n is the number of queries and m is the number of balls. This is because, for each query, performing a linear scan to count the distinct colors takes O(m) time.
  • 🧺 Space complexity: O(m) for storing the balls in balls array.

Method 2 - Using array for balls and map for colors

We have to track the:

  • color of each ball to update and check existing colors, and
  • number of occurrences for each color to efficiently calculate distinct colors.

For that we can use:

  • An array (balls) where the index represents the ball and the value at that index represents the current color of the ball.
  • A hashmap (colorMap) to maintain the count of each color.

Here is the approach:

  1. Initialization:
    • n: number of queries.
    • ans: array for the number of distinct colors after each query.
    • balls: array to track the color of each ball.
    • colorMap: hashmap for color counts.
  2. Iterate Through Queries: For each query:
    • Extract ball and color.
    • If the ball already has a color, adjust colorMap.
    • Update the ball’s color in balls.
    • Update the new color count in colorMap.
    • Store the count of distinct colors in ans.
  3. Final Result: Return the ans array.

Code

Java
class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        Map<Integer, Integer> colorMap = new HashMap<>();
        int[] balls = new int[limit + 1];

        for (int i = 0; i < n; i++) {
            int ball = queries[i][0];
            int color = queries[i][1];

            if (balls[ball] != 0) {
                int prevColor = balls[ball];
                colorMap.put(prevColor, colorMap.get(prevColor) - 1);

                if (colorMap.get(prevColor) == 0) {
                    colorMap.remove(prevColor);
                }
            }

            balls[ball] = color;
            colorMap.put(color, colorMap.getOrDefault(color, 0) + 1);

            ans[i] = colorMap.size();
        }
        return ans;
    }
}
Python
class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        n = len(queries)
        ans = [0] * n
        color_map: Dict[int, int] = {}
        balls = [0] * (limit + 1)

        for i, (ball, color) in enumerate(queries):
            if balls[ball] != 0:
                prev_color = balls[ball]
                color_map[prev_color] = color_map.get(prev_color, 0) - 1

                if color_map[prev_color] == 0:
                    del color_map[prev_color]

            balls[ball] = color
            color_map[color] = color_map.get(color, 0) + 1

            ans[i] = len(color_map)

        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is the number of queries, as each query involves constant-time operations for updating the arrays and hashmap.
  • 🧺 Space complexity: O(n + m) where m is the limit (number of distinct ball labels), because we need to store color information for up to m + 1 balls and at most n distinct colors in colormap.

Method 3 - Using 2 maps

The main challenge in the previous solution is the large memory usage due to the array of size limit + 1. Given that limit can be as large as 10^9, using such a huge array is excessive, especially since not all ball labels are accessed in the queries (with n ranging up to 10^5).

To improve storage efficiency, we can eliminate wasted space by using a hashmap to store only the necessary ball labels accessed by the queries. This will significantly optimize space complexity and prevent memory overuse.

By using hashmaps for both the ball labels and colors, we maintain the same logic as before but with much more efficient memory usage. This allows us to process and track query results while staying within the memory limits.a

Code

Java
class Solution {
    public int[] queryResults(int limit, int[][] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        Map<Integer, Integer> colorMap = new HashMap<>();
        Map<Integer, Integer> ballMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int ball = queries[i][0];
            int color = queries[i][1];

            if (ballMap.containsKey(ball)) {
                int prevColor = ballMap.get(ball);
                colorMap.put(prevColor, colorMap.get(prevColor) - 1);

                if (colorMap.get(prevColor) == 0) {
                    colorMap.remove(prevColor);
                }
            }

            ballMap.put(ball, color);
            colorMap.put(color, colorMap.getOrDefault(color, 0) + 1);

            ans[i] = colorMap.size();
        }
        return ans;
    }
}
Python
class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        n = len(queries)
        ans = [0] * n
        color_map: Dict[int, int] = {}
        ball_map: Dict[int, int] = {}

        for i, (ball, color) in enumerate(queries):
            if ball in ball_map:
                prev_color = ball_map[ball]
                color_map[prev_color] -= 1

                if color_map[prev_color] == 0:
                    del color_map[prev_color]

            ball_map[ball] = color
            color_map[color] = color_map.get(color, 0) + 1

            ans[i] = len(color_map)

        return ans

Complexity

  • ⏰ Time complexity: O(n). The algorithm processes each query once, performing O(1) operations on average for each due to hashmaps. Thus, the overall time complexity is O(n).
  • 🧺 Space complexity: O(n). ballMap and colorMap together can store up to n entries in total, resulting in a space complexity of O(n). The result array also contributes O(n) space, but it is typically part of the output.