Distinct Numbers in Each Subarray

Distinct Numbers in Each Subarray

What is this problem about?

The Distinct Numbers in Each Subarray coding problem gives you an array of integers and an integer $k$. You need to return an array of size $n-k+1$ where each element is the count of unique (distinct) numbers in every contiguous subarray of length $k$.

Why is this asked in interviews?

Amazon frequently asks this question to test a candidate's proficiency with the Sliding Window interview pattern combined with Hash Tables. It evaluation whether you can efficiently update a frequency state as you move through an array. This is a fundamental optimization problem where the goal is to avoid the $O(n \times k)$ cost of a nested loop by using $O(n)$ linear traversal.

Algorithmic pattern used

This problem uses a Sliding Window with a Frequency Map.

1. Initialize a Hash Map to store the frequencies of elements in the first $k$ elements.
2. The number of unique elements is the current size of the map.
3. Slide the window one step at a time:
   • Add the new element entering the window to the map (increment its count).
   • Remove the element leaving the window from the map (decrement its count).
   • If an element's count reaches zero, remove it from the map entirely.
4. Record the size of the map after each slide.

Example explanation

Array: [1, 2, 1, 3, 4, 2, 3], $k=3$

1. First Window [1, 2, 1]: Frequencies: {1: 2, 2: 1}. Distinct count = 2.
2. Slide to [2, 1, 3]: Add 3, remove 1. Frequencies: {1: 1, 2: 1, 3: 1}. Distinct count = 3.
3. Slide to [1, 3, 4]: Add 4, remove 2. Frequencies: {1: 1, 3: 1, 4: 1}. Distinct count = 3.
4. Slide to [3, 4, 2]: Add 2, remove 1. Frequencies: {3: 1, 4: 1, 2: 1}. Distinct count = 3.
5. Slide to [4, 2, 3]: Add 3, remove 3... wait, if $k=3$, the logic continues until the end.

Common mistakes candidates make

• Failing to remove keys: Only decrementing the count in the map but leaving the key with value 0. This keeps the map size incorrect.
• Brute Force: Using a new Set for every window, which is $O(n \times k)$.
• Off-by-one errors: Incorrectly calculating the indices for the element to remove.

Interview preparation tip

Whenever a problem asks for "count of something in all subarrays of size K," think Sliding Window + Hash Map. Practice the logic of "one in, one out" to maintain a running state. If the elements are within a small range (e.g., $1 \dots 10^5$), an array of size $10^5$ can be faster than a Hash Map.