LeetCode Problem 1852

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

LeetCode 1852 - Distinct Numbers in Each Subarray

Problem Understanding

The problem gives us an integer array nums and an integer k. For every contiguous subarray of length k, we must determine how many unique values appear inside that window.

A subarray is a continuous portion of the array. Since the window size is fixed at k, the first subarray is nums[0:k], the next is nums[1:k+1], and so on until the final valid window.

For each window, we count how many distinct integers it contains. The result array should store these counts in order.

For example, if:

nums = [1,2,3,2,2,1,3]
k = 3

Then the windows are:

[1,2,3] -> 3 distinct
[2,3,2] -> 2 distinct
[3,2,2] -> 2 distinct
[2,2,1] -> 2 distinct
[2,1,3] -> 3 distinct

So the answer becomes:

[3,2,2,2,3]

The constraints are important:

1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5

An array size of 100000 means we must design an efficient algorithm. Any solution that repeatedly scans every window from scratch will become too slow.

The key challenge is avoiding redundant work between overlapping windows. Consecutive windows share most of their elements, so recalculating everything each time is wasteful.

Some important edge cases include:

• k = 1, every window contains exactly one element, so every answer is 1.
• k = nums.length, there is only one window covering the entire array.
• Arrays with all identical values, where every window has only one distinct element.
• Arrays where every value is different, where each window has exactly k distinct elements.
• Repeated insertions and removals of the same value as the sliding window moves.

The problem guarantees valid input sizes and valid window sizes, so we do not need to handle invalid cases such as k > len(nums).

Approaches

Brute Force Approach

The most straightforward solution is to process every subarray independently.

For each starting index i, we take the subarray:

nums[i : i + k]

We insert all elements of that subarray into a hash set, then measure the set size. Since sets only store unique values, the size of the set equals the number of distinct elements.

This approach is correct because every window is examined independently and every distinct value is counted exactly once.

However, this solution is inefficient. There are approximately n - k + 1 windows, and each window requires up to k insertions into a set.

The total complexity becomes:

O((n - k + 1) * k)

In the worst case, this becomes O(n * k), which can reach 10^10 operations when both n and k are large.

Optimal Approach, Sliding Window with Frequency Map

The important observation is that adjacent windows overlap heavily.

Suppose we move from:

[1,2,3]

to:

[2,3,2]

Most elements remain the same. Only:

• one element leaves the window
• one element enters the window

Instead of rebuilding the distinct count from scratch, we can maintain a frequency map for the current window.

The frequency map stores:

value -> count inside current window

When the window slides:

• decrement the frequency of the outgoing element
• remove it from the map if its count becomes zero
• increment the frequency of the incoming element

At any moment, the number of distinct elements equals the number of keys in the frequency map.

This allows every element to be processed only a constant number of times, giving an O(n) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(k)	Rebuilds a set for every window
Optimal	O(n)	O(k)	Uses sliding window and frequency counting

Algorithm Walkthrough

1. Create an empty frequency map.

The map will store how many times each number appears in the current window. 2. Build the first window.

Iterate through the first k elements and increment their counts in the frequency map. 3. Record the number of distinct elements.

The number of unique values equals the number of keys currently stored in the frequency map. 4. Start sliding the window one position at a time.

For each new position:

• Remove the outgoing element, which is the leftmost value from the previous window.
• Decrease its frequency.
• If its frequency becomes zero, remove it entirely from the map.
• Add the incoming element, which is the new rightmost value entering the window.
• Increase its frequency in the map.

5. After updating the window, append the number of distinct elements.

Again, the distinct count equals the number of keys in the frequency map. 6. Continue until all windows are processed.

Why it works

The sliding window always represents exactly one contiguous subarray of size k.

The frequency map maintains the exact count of every number currently inside the window. When an element leaves the window, its count is decreased. When a new element enters, its count is increased.

A number is distinct if and only if its frequency is greater than zero. Therefore, the number of keys in the frequency map always equals the number of distinct elements in the current window.

Because the window updates are performed correctly at every step, the algorithm produces the correct answer for every subarray.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
        frequency = defaultdict(int)
        result = []

        # Build the first window
        for i in range(k):
            frequency[nums[i]] += 1

        result.append(len(frequency))

        # Slide the window
        for right in range(k, len(nums)):
            left = right - k

            outgoing = nums[left]
            frequency[outgoing] -= 1

            if frequency[outgoing] == 0:
                del frequency[outgoing]

            incoming = nums[right]
            frequency[incoming] += 1

            result.append(len(frequency))

        return result

The implementation begins by creating a frequency map using defaultdict(int). This allows frequencies to be incremented without manually checking whether a key already exists.

The first loop constructs the initial window of size k. Each number is added into the frequency map, and after the loop completes, the number of keys in the map equals the number of distinct values in the first window.

The second loop handles the sliding process. For every new window position:

• the outgoing element is removed
• the incoming element is added
• the distinct count is appended to the result

If an outgoing element's frequency reaches zero, it must be removed from the dictionary entirely. Otherwise, the dictionary would incorrectly count it as still present in the window.

The algorithm never rebuilds the window from scratch, which is why it runs efficiently in linear time.

Go Solution

func distinctNumbers(nums []int, k int) []int {
	frequency := make(map[int]int)
	result := []int{}

	// Build the first window
	for i := 0; i < k; i++ {
		frequency[nums[i]]++
	}

	result = append(result, len(frequency))

	// Slide the window
	for right := k; right < len(nums); right++ {
		left := right - k

		outgoing := nums[left]
		frequency[outgoing]--

		if frequency[outgoing] == 0 {
			delete(frequency, outgoing)
		}

		incoming := nums[right]
		frequency[incoming]++

		result = append(result, len(frequency))
	}

	return result
}

The Go implementation follows the same logic as the Python version.

Go uses a built in map[int]int instead of Python's dictionary. When removing an element whose frequency becomes zero, the delete() function is used to completely remove the key from the map.

Slices are used for storing the result array. Since Go maps return the zero value for missing keys, incrementing frequencies is straightforward without extra existence checks.

There are no integer overflow concerns because the frequencies never exceed k, and k <= 100000.

Worked Examples

Example 1

nums = [1,2,3,2,2,1,3]
k = 3

Build Initial Window

Window:

[1,2,3]

Frequency map:

Number	Count
1	1
2	1
3	1

Distinct count:

3

Result:

[3]

Slide Window to [2,3,2]

Outgoing element:

1

Incoming element:

2

Updated frequency map:

Number	Count
2	2
3	1

Distinct count:

2

Result:

[3,2]

Slide Window to [3,2,2]

Outgoing element:

2

Incoming element:

2

Frequency map remains:

Number	Count
2	2
3	1

Distinct count:

2

Result:

[3,2,2]

Slide Window to [2,2,1]

Outgoing element:

3

Incoming element:

1

Updated frequency map:

Number	Count
2	2
1	1

Distinct count:

2

Result:

[3,2,2,2]

Slide Window to [2,1,3]

Outgoing element:

2

Incoming element:

3

Updated frequency map:

Number	Count
2	1
1	1
3	1

Distinct count:

3

Final result:

[3,2,2,2,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the window once
Space	O(k)	The frequency map stores at most k distinct values

The algorithm processes every array element a constant number of times. Each value is added to the frequency map once and removed once.

The frequency map can contain at most k unique elements because the window size is fixed at k.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
        frequency = defaultdict(int)
        result = []

        for i in range(k):
            frequency[nums[i]] += 1

        result.append(len(frequency))

        for right in range(k, len(nums)):
            left = right - k

            outgoing = nums[left]
            frequency[outgoing] -= 1

            if frequency[outgoing] == 0:
                del frequency[outgoing]

            incoming = nums[right]
            frequency[incoming] += 1

            result.append(len(frequency))

        return result

solution = Solution()

assert solution.distinctNumbers([1,2,3,2,2,1,3], 3) == [3,2,2,2,3]  # example 1
assert solution.distinctNumbers([1,1,1,1,2,3,4], 4) == [1,2,3,4]  # example 2
assert solution.distinctNumbers([5], 1) == [1]  # single element
assert solution.distinctNumbers([1,2,3,4], 1) == [1,1,1,1]  # k = 1
assert solution.distinctNumbers([1,2,3,4], 4) == [4]  # entire array as one window
assert solution.distinctNumbers([7,7,7,7,7], 2) == [1,1,1,1]  # all identical
assert solution.distinctNumbers([1,2,3,4,5], 3) == [3,3,3]  # all unique
assert solution.distinctNumbers([1,2,1,2,1,2], 2) == [2,2,2,2,2]  # alternating values
assert solution.distinctNumbers([1,1,2,2,3,3], 3) == [2,2,2,2]  # repeated grouped values

Test Summary

Test	Why
[1,2,3,2,2,1,3], k=3	Validates the primary example
[1,1,1,1,2,3,4], k=4	Tests increasing distinct counts
[5], k=1	Smallest valid input
[1,2,3,4], k=1	Every window contains one element
[1,2,3,4], k=4	Window equals entire array
[7,7,7,7,7], k=2	All values identical
[1,2,3,4,5], k=3	Every window fully distinct
[1,2,1,2,1,2], k=2	Repeated alternating pattern
[1,1,2,2,3,3], k=3	Tests frequency decrement correctness

Edge Cases

One important edge case occurs when k = 1. In this situation, every window contains exactly one element, so the answer must always be 1. A buggy implementation might overcomplicate the logic or incorrectly maintain frequencies across windows. This solution handles it naturally because each window contains a single key in the frequency map.

Another important case is when all numbers are identical. For example:

[7,7,7,7,7]

Every window should have exactly one distinct value. Implementations that forget to decrement frequencies properly may accidentally count duplicate values multiple times. The frequency map ensures duplicates are tracked correctly.

A third critical edge case appears when an outgoing element completely disappears from the window. For example:

[1,2,3]

sliding to:

[2,3,4]

The value 1 must be removed from the frequency map after its count becomes zero. If the key is left in the map, the distinct count becomes incorrect. The implementation explicitly deletes zero frequency entries to avoid this bug.

A final edge case occurs when the entire array forms a single window, meaning k = len(nums). In this case, there is only one answer value. The implementation handles this correctly because it builds the initial window and immediately returns the correct result without entering the sliding loop.