Tejav
#3160

Find the Number of Distinct Colors Among the Balls

Medium
ArrayHash TableSimulationHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Using two hash maps allows us to efficiently track colors and their counts, reducing the need to repeatedly count distinct colors after each query.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a map to store the color of each ball and another map to count how many balls have each color.
  2. 2Step 2: For each query, update the color of the specified ball and adjust the color counts accordingly.
  3. 3Step 3: After each update, record the number of distinct colors based on the color count map.
solution.py14 lines
1def countDistinctColors(limit, queries):
2    ball_colors = {}
3    color_count = {}
4    result = []
5    for x, y in queries:
6        if x in ball_colors:
7            old_color = ball_colors[x]
8            color_count[old_color] -= 1
9            if color_count[old_color] == 0:
10                del color_count[old_color]
11        ball_colors[x] = y
12        color_count[y] = color_count.get(y, 0) + 1
13        result.append(len(color_count))
14    return result
ℹ

Complexity note: The time complexity is O(n) because we process each query in constant time, and the space complexity is O(n) due to the storage of colors and counts.

  • 1Using hash maps allows for efficient color tracking.
  • 2Avoid unnecessary counting by maintaining counts of colors.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.