We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of Distinct Colors Among the Balls

Number: 3434

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg

Problem Description

You are given an integer limit and a 2D array queries where each query is of the form [x, y]. There are limit+1 balls, labeled from 0 to limit, and initially, all balls are uncolored. For every query, you color ball x with color y and then determine the number of distinct colors present among all balls (ignoring balls that remain uncolored). Return an array result of length equal to the number of queries, where result[i] denotes the number of distinct colors after the i-th query.

Key Insights

  • Use a dictionary (or hash map) to track the current color for each ball.
  • Use another dictionary (or hash map) to count the frequency of each color that is actively used.
  • When updating the color of a ball, decrement the frequency of the old color, and if its count reaches zero, remove it.
  • Increment the frequency of the new color and record the current number of distinct colors.

Space and Time Complexity

Time Complexity: O(n) on average, where n is the number of queries, since each query performs O(1) operations. Space Complexity: O(n) in the worst case for storing the ball-to-color mapping and the color frequency counts.

Solution

The solution primarily uses two hash maps (dictionaries): one to store the current color of each ball and another to store the frequency of each color that has been applied. For every query:

  1. Check if the ball already has a color. If yes, decrement the count for that color and remove it if the count becomes zero.
  2. Update the ball’s color with the new color and increment the frequency for the new color.
  3. After processing the query, the number of keys in the frequency map gives the number of distinct colors currently in use. This approach ensures that each query is processed in O(1) average time.

Code Solutions

# Python solution with detailed comments

def distinctColors(limit, queries):
    # Dictionary to keep track of the current color of each ball
    ball_color = {}
    # Dictionary to count the frequency of each color applied
    color_count = {}
    # List to store the results after each query
    results = []
    
    # Process each query one by one
    for ball, color in queries:
        # If the ball has been colored before, update the old color frequency
        if ball in ball_color:
            old_color = ball_color[ball]
            color_count[old_color] -= 1  # Decrement the count of the old color
            # If the frequency becomes zero, remove the color from the dictionary
            if color_count[old_color] == 0:
                del color_count[old_color]
        
        # Update ball's color to the new color
        ball_color[ball] = color
        # Increase the frequency count of the new color
        color_count[color] = color_count.get(color, 0) + 1
        
        # The number of distinct colors is the number of keys in color_count
        results.append(len(color_count))
    
    return results

# Example usage:
# limit = 4
# queries = [[1,4],[2,5],[1,3],[3,4]]
# print(distinctColors(limit, queries))  # Output: [1,2,2,3]
← Back to All Questions