Daily Leetcode – 3160

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 i-th query.

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

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

My Solution

Initially I tried using an array based solution, however due to the large potential value of limit and value of colors, I realized that was not the way to go.

The problem can be efficiently solved using hashmaps. Since limit is large, storing all limit + 1 balls explicitly would be inefficient. Instead, we maintain only the colored balls in a hashmap and track the count of each color separately.

Approach

1. Maintain a counter (distinct) for the number of distinct colors.

   • If a new color is introduced, increment distinct.
   • If a color count drops to zero, decrement distinct.

2. Use an unordered_map to track each ball's color.

   • If a ball is assigned a new color, update the record.

3. Use another unordered_map (color_count) to track occurrences of each color.

   • If a balls color is changed, increment the new_color count and decrement the old_color count.
   • If this is the first occurence of new_color, then increment the distinct colors counter.
   • If the count of old_color becomes 0, decrement the distinct colors counter.

Here's an implementation in C++:

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) {
        vector<int> result;
        unordered_map<int,int> ball_color;
        unordered_map<int,int> color_count;
        int distinct = 0;
        for(auto& query : queries) {
            int ball = query[0];
            int new_color = query[1];
            int old_color = ball_color[ball];
            if(old_color != new_color) {
                distinct += (++color_count[new_color] == 1);
                distinct -= (--color_count[old_color] == 0);
                ball_color[ball] = new_color;
            }
            result.push_back(distinct);
        }
        return result;
    }
};

Algorithm Analysis

Time Complexity

Since each query is processed in O(1) on average using hashmaps, the total complexity is O(n), where n is the number of queries.

Space Complexity

In the worst case, we have to store the color of each ball in [0,limit], as well as the count of each color. Thus, the worst-case space complexity is O(n), as we store up to n unique balls and their associated colors.

Results

Runtime: 115 ms, beating **57.23% **of submissions.

Memory Usage: 157.48 MB, beating **60.45% **of submissions.

Although I'm not in the high 90's, I think this could be a result of testing randomization.