Skip to content

← leetcode

Find the Number of Distinct Colors Among the Balls

· Medium

LeetCode problem 3160

I am not going to lie, this question spoke to me and told me to use some hashmaps; two to be specific.

The unordered_maps that I had to initalise were ball and colour_count:

  • ball is used to keep track of what each ball's colour is
  • colour_count is used to keep track of the number of balls in each colour.

Then, I just iterated through the queries, maintaining a temp variable to keep track of the number of unique colours present:

  • if define each pair in queries to be [ball_number, colour_number], then if ball[ball_number] has a colour, then we need to subtract 1 from colour_count[ball[ball_number]] as we are painting over the original colour
    • we also need to account for that fact that if colour_count[ball[ball_number]] == 0 after subtraction, then we can erase colour_count[ball[ball_number]] and subtract 1 from temp as there is 1 less colour present
  • then, we just make ball[ball_number] = colour_number, increment colour_count[colour_number] and add 1 to temp if colour_count[colour_number] did not exist previously.

code

class Solution {
public:
    vector<int> queryResults(int limit, vector<vector<int>>& queries) {
        unordered_map<int, int> ball;
        unordered_map<int, int> colour_count;

        vector<int> ans;
        int temp = 0;
        for (auto &pair : queries) {
            if (ball[pair[0]]) {
                --colour_count[ball[pair[0]]];
                if (colour_count[ball[pair[0]]] == 0) {
                    colour_count.erase(ball[pair[0]]);
                    --temp;
                }
            }
            ball[pair[0]] = pair[1];

            if (!colour_count[pair[1]]) {
                ++temp;
            }
            ++colour_count[pair[1]];

            ans.push_back(temp);
        }
        return ans;
    }
};

complexity

  • Time: O(n)
  • Space: O(n)