Today’s problem

https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls/description

Intuition

All we need to know is how many colors left in the list. Then we can store how many balls do one color have. If there are 0 balls left, then col_cnt -= 1. If there appears a new color, then col_cnt += 1.

Approach

• Store a buket for every ball and every color.
• Change the color of one ball.
• If there are 0 balls left, then col_cnt -= 1.
• If there appears a new color, then col_cnt += 1.

Complexity

• Time complexity: $O(N)$, N is the length of the query.

• Space complexity: $O(N)$, N is the length of the query.

Potential follow up question

Now I want to change the color of a section? For example, now the imput change into (x,y,z), changing the color of the balls from x to y (inclusive) to z. Then tell me how many balls have distinct colors?

Code

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        col = 0
        ans = []
        visCol = dict()
        balCol = dict()
        for (x, y) in queries:
            if x in balCol:
                visCol[balCol[x]] -= 1
                if visCol[balCol[x]] == 0:
                    col -= 1
            balCol.update({x: y})
            if (y not in visCol) or (visCol[y] == 0):
                col += 1
                visCol.update({y: 1})
            else:
                visCol[y] += 1
        
            ans.append(col)
        
        return ans