Find the Number of Distinct Colors Among the Balls

Leetcode Problem:

• Find the Number of Distinct Colors Among the Balls

Summary

• Given a limit and a 2D array of queries, find the number of distinct colors among the balls after each query.

Approach

• The solution uses two unordered maps to keep track of the color count and the current color of each ball
• It iterates over the queries, updating the color count and current color of each ball, and pushes the number of distinct colors to the result vector.

Complexity

• O(n), where n is the number of queries

Explain

• The solution starts by initializing two unordered maps, colorCnt to store the count of each color and curColor to store the current color of each ball
• It also initializes a variable colornum to store the number of distinct colors
• Then, it iterates over the queries, updating the color count and current color of each ball
• If the current color of a ball is the same as its query color, it pushes the current number of distinct colors to the result vector and continues to the next query
• If the current color of a ball is not the same as its query color, it decrements the count of the current color and increments the count of the query color
• Finally, it pushes the updated number of distinct colors to the result vector.

Solution Code:

class Solution {
public:
    vector queryResults(int limit, vector>& queries) {
        unordered_map colorCnt;
        unordered_map curColor;
        vector ans;
        int colornum = 0;
        for(int i = 0 ; i < queries.size(); i++){
            int idx = queries[i][0];
            int color = queries[i][1];
            if(curColor[idx] == color){
                ans.push_back(colornum);
                continue;
            }
            if (colorCnt[curColor[idx]] > 0){
                colorCnt[curColor[idx]]--;
                if(colorCnt[curColor[idx]] == 0){
                    colornum--;
                }
            }
            if(colorCnt[color] == 0){
                colornum++;
            }
            curColor[idx] = color;
            colorCnt[color]++;
             
            ans.push_back(colornum);
        }
        return ans;
    }
};