Problem Description

You have an integer array nums with length n and an integer k. You need to find how many distinct (unique) elements exist in every subarray of size k.

A subarray of size k means k consecutive elements from the array. For example, if nums = [1, 2, 3, 4] and k = 3, the subarrays of size 3 are: [1, 2, 3] and [2, 3, 4].

Your task is to return an array ans where:

• ans[i] represents the count of distinct elements in the subarray starting at index i and ending at index i + k - 1
• The result array will have length n - k + 1 (one result for each possible subarray of size k)

For example:

• If nums = [1, 2, 1, 3, 4] and k = 3
• Subarray [1, 2, 1] has 2 distinct elements (1 and 2)
• Subarray [2, 1, 3] has 3 distinct elements (1, 2, and 3)
• Subarray [1, 3, 4] has 3 distinct elements (1, 3, and 4)
• So the answer would be [2, 3, 3]

The solution uses a sliding window technique with a hash table (Counter) to efficiently track distinct elements. It maintains a window of size k and slides it through the array, updating the count of distinct elements by adding the new element entering the window and removing the element leaving the window.

Intuition

The naive approach would be to check each subarray of size k independently, counting distinct elements for each one. However, this would involve redundant work since consecutive subarrays overlap significantly - they share k-1 elements.

Consider two consecutive subarrays: nums[i..i+k-1] and nums[i+1..i+k]. The second subarray is almost identical to the first, except it loses one element from the left (nums[i]) and gains one element on the right (nums[i+k]). This observation leads us to the sliding window technique.

Instead of recounting distinct elements from scratch for each subarray, we can maintain a running count:

1. Start with the first window of size k and count its distinct elements
2. To move to the next window, we simply:
   • Remove the leftmost element that's sliding out
   • Add the new rightmost element that's sliding in
   • Update our distinct count accordingly

The key insight is using a frequency map (hash table) to track not just which elements are present, but how many times each appears. This is crucial because:

• When adding a new element, we increment its count
• When removing an element, we decrement its count
• If an element's count drops to 0, it's no longer in the window and should be removed from our map
• The number of distinct elements is simply the size of our frequency map

This transforms an O(n * k) problem (checking each subarray independently) into an O(n) solution, as we only process each element twice - once when it enters the window and once when it leaves.

Learn more about Sliding Window patterns.

Solution Approach

We implement the sliding window technique using a hash table to efficiently track distinct elements in each subarray of size k.

Step 1: Initialize the first window

• Create a Counter (hash table) called cnt to store the frequency of elements
• Add the first k elements from nums to cnt
• The number of distinct elements in the first window is len(cnt) (the number of keys in the hash table)
• Initialize the answer array with this count: ans = [len(cnt)]

Step 2: Slide the window through the array

• Iterate through the remaining elements starting from index k to the end of the array

• For each new position i:

  Add the new element (right side of window):

  • Increment the count of nums[i] in the hash table: cnt[nums[i]] += 1

  Remove the old element (left side of window):

  • Decrement the count of nums[i - k] in the hash table: cnt[nums[i - k]] -= 1
  • If the count becomes 0, remove this element from the hash table entirely: cnt.pop(nums[i - k])
  • This removal is crucial because we only want to count distinct elements that are actually present in the current window

  Record the distinct count:

  • After updating the hash table, len(cnt) gives us the number of distinct elements in the current window
  • Append this count to the answer array: ans.append(len(cnt))

Step 3: Return the result

• After processing all windows, return the ans array containing the distinct element counts for each subarray

The time complexity is O(n) where n is the length of the input array, as we process each element exactly twice (once when entering the window, once when leaving). The space complexity is O(k) for the hash table storing at most k distinct elements.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 1, 3, 4] and k = 3.

Initial Setup:

• We need to find distinct elements in each subarray of size 3
• Expected subarrays: [1,2,1], [2,1,3], [1,3,4]

Step 1: Initialize the first window [1, 2, 1]

• Create a Counter: cnt = {}
• Add first 3 elements:
  • Add nums[0] = 1: cnt = {1: 1}
  • Add nums[1] = 2: cnt = {1: 1, 2: 1}
  • Add nums[2] = 1: cnt = {1: 2, 2: 1}
• Distinct count = len(cnt) = 2 (keys are 1 and 2)
• Initialize answer: ans = [2]

Step 2: Slide to second window [2, 1, 3]

• Current window needs to lose nums[0] = 1 and gain nums[3] = 3
• Add new element nums[3] = 3:
  • cnt[3] += 1 → cnt = {1: 2, 2: 1, 3: 1}
• Remove old element nums[0] = 1:
  • cnt[1] -= 1 → cnt = {1: 1, 2: 1, 3: 1}
  • Since cnt[1] = 1 (not 0), we keep it in the map
• Distinct count = len(cnt) = 3
• Update answer: ans = [2, 3]

Step 3: Slide to third window [1, 3, 4]

• Current window needs to lose nums[1] = 2 and gain nums[4] = 4
• Add new element nums[4] = 4:
  • cnt[4] += 1 → cnt = {1: 1, 2: 1, 3: 1, 4: 1}
• Remove old element nums[1] = 2:
  • cnt[2] -= 1 → cnt = {1: 1, 2: 0, 3: 1, 4: 1}
  • Since cnt[2] = 0, remove it: cnt = {1: 1, 3: 1, 4: 1}
• Distinct count = len(cnt) = 3
• Final answer: ans = [2, 3, 3]

The sliding window efficiently tracks distinct elements by maintaining frequencies, only updating the elements that change as the window moves.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the array nums.

The algorithm initializes a Counter with the first k elements, which takes O(k) time. Then it iterates through the remaining n - k elements. For each element, it performs the following constant-time operations:

• Adding an element to the counter: O(1)
• Decrementing a counter value: O(1)
• Checking if a value equals zero: O(1)
• Potentially removing an element from the counter: O(1)
• Getting the length of the counter: O(1)
• Appending to the result list: O(1)

Since we iterate through n - k elements with constant-time operations per iteration, and the initial setup is O(k), the total time complexity is O(k) + O(n - k) = O(n).

Space Complexity: O(k) where k is the window size parameter.

The Counter maintains at most k distinct elements at any given time (representing the elements in the current window). The result list ans stores n - k + 1 values, which is O(n) space. However, since the result list is part of the output and typically not counted in space complexity analysis for the algorithm itself, the auxiliary space complexity is determined by the Counter, which is O(k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Remove Zero-Count Elements from the Hash Table

The Pitfall: A frequent mistake is decrementing the count of the element leaving the window but forgetting to remove it from the hash table when its count reaches zero. This leads to incorrect distinct element counts because len(cnt) would include keys with zero values.

Incorrect Implementation:

# WRONG: Only decrements but doesn't remove
window_counter[nums[i - k]] -= 1
result.append(len(window_counter))  # This will be incorrect!

Why This Fails: If an element's count becomes 0, it's no longer in the current window but still exists as a key in the hash table. The len(window_counter) would count it as a distinct element even though it shouldn't be included.

Correct Solution:

window_counter[nums[i - k]] -= 1
if window_counter[nums[i - k]] == 0:
    window_counter.pop(nums[i - k])  # Critical step!
result.append(len(window_counter))

2. Using a Set Instead of a Counter

The Pitfall: Attempting to use a set to track distinct elements seems logical but fails when elements have multiple occurrences within the window.

Incorrect Implementation:

# WRONG: Using a set
window_set = set(nums[:k])
result = [len(window_set)]

for i in range(k, len(nums)):
    window_set.add(nums[i])
    window_set.discard(nums[i - k])  # Problem: removes even if multiple occurrences exist!

Why This Fails: Consider nums = [1, 1, 2] with k = 3. When sliding to the next window, removing the first 1 would incorrectly remove 1 from the set entirely, even though another 1 remains in the window.

Correct Solution: Use a Counter/hash table to track frequencies, only removing elements when their count reaches zero.

3. Off-by-One Errors in Window Boundaries

The Pitfall: Incorrectly calculating which element to remove when sliding the window.

Common Mistakes:

# WRONG: Removes wrong element
window_counter[nums[i - k + 1]] -= 1  # Should be nums[i - k]

# WRONG: Incorrect initial window size
window_counter = Counter(nums[:k-1])  # Should be nums[:k]

Correct Solution:

• The element to remove is at index i - k (exactly k positions behind the current element)
• The initial window should include exactly k elements: nums[0:k]

4. Not Handling Edge Cases

The Pitfall: Not considering special cases like k = 1, k = n, or empty arrays.

Correct Handling:

def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
  
    # Rest of the implementation...

These edge cases are typically handled naturally by the sliding window approach, but explicit checks can prevent unexpected behavior.