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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Distinct Numbers in Each Subarray

Number: 2003

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an integer array nums and an integer k, find the number of distinct elements in every contiguous subarray of size k. For each sliding window, return the count of unique elements in that window.

Key Insights

  • Use a sliding window to traverse the array with a fixed window size k.
  • Leverage a hash table (dictionary or map) to count the frequency of elements within the current window.
  • As the window slides, decrement the count of the element going out and increment (or add) the count of the new element coming in.
  • When the count of an element drops to zero, remove it from the hash table to maintain an accurate count of distinct elements.

Space and Time Complexity

Time Complexity: O(n) – Each element is processed a constant number of times. Space Complexity: O(k) – The hash table stores up to k elements in the worst-case scenario.

Solution

We implement a sliding window approach with a hash table (or dictionary in Python; map in Java/C++) to track the frequencies of each element in the current window. Initially, populate the hash table with the first k elements and record the number of distinct keys. Then, for each step, slide the window by one position: decrement the frequency of the outgoing element and remove it from the hash table if its frequency becomes zero; increment or add the new incoming element’s frequency. Append the current number of distinct keys to the answer list. This efficiently computes the result for each window.

Code Solutions

# Python solution
def distinctNumbers(nums, k):
    # Import defaultdict for convenient frequency counting
    from collections import defaultdict
    
    frequency = defaultdict(int)  # Hash table to store frequency of elements
    result = []
    
    # Initialize the first window of size k
    for i in range(k):
        frequency[nums[i]] += 1
    
    # Append the count of distinct numbers in the first window
    result.append(len(frequency))
    
    # Slide the window from position 1 to (len(nums) - k)
    for i in range(k, len(nums)):
        # Element going out of the window
        outgoing = nums[i - k]
        frequency[outgoing] -= 1
        # Remove the element if its frequency becomes 0
        if frequency[outgoing] == 0:
            del frequency[outgoing]
        
        # Add the new incoming element
        frequency[nums[i]] += 1
        
        # Append current count of distinct elements
        result.append(len(frequency))
    
    return result

# Example usage
print(distinctNumbers([1,2,3,2,2,1,3], 3))
← Back to All Questions