You are given an integer array nums of length n and an integer k. Your task is to find the number of distinct elements in every subarray of size k within nums.
Return an array ans such that ans[i] is the count of distinct elements in nums[i..(i + k - 1)] for each index 0 <= i < n - k.
Example 1:
Input: nums = [1,2,3,2,2,1,3], k = 3 Output: [3,2,2,2,3] Explanation: The number of distinct elements in each subarray goes as follows: - nums[0..2] = [1,2,3] so ans[0] = 3 - nums[1..3] = [2,3,2] so ans[1] = 2 - nums[2..4] = [3,2,2] so ans[2] = 2 - nums[3..5] = [2,2,1] so ans[3] = 2 - nums[4..6] = [2,1,3] so ans[4] = 3
Example 2:
Input: nums = [1,1,1,1,2,3,4], k = 4 Output: [1,2,3,4] Explanation: The number of distinct elements in each subarray goes as follows: - nums[0..3] = [1,1,1,1] so ans[0] = 1 - nums[1..4] = [1,1,1,2] so ans[1] = 2 - nums[2..5] = [1,1,2,3] so ans[2] = 3 - nums[3..6] = [1,2,3,4] so ans[3] = 4
Constraints:
1 <= k <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: Given an integer array nums and an integer k, compute how many distinct numbers appear in every contiguous subarray of size k. For each window of length k, return the number of unique values inside that window.
This is a classic fixed-size window problem. Instead of recomputing the distinct count for every subarray from scratch, you maintain information about the current window and update it as the window slides forward.
Approach 1: Sliding Window + Hash Table (O(n) time, O(k) space)
Maintain a frequency map using a hash table while sliding a window of size k across the array. As you expand the window to the right, increment the count of nums[right] in the map. When the window exceeds size k, remove the leftmost element by decrementing its frequency and deleting it from the map if the count reaches zero. The number of keys in the map always equals the number of distinct elements in the current window. Each element is inserted and removed at most once, producing O(n) total operations with O(k) space for the map. This approach relies on efficient hash lookups and is the standard technique for fixed-size windows in sliding window problems.
Approach 2: Sliding Window + Array Frequency (O(n) time, O(R) space)
If the values in nums fall within a limited range, you can replace the hash table with a direct-access frequency array. The logic stays identical: increment the frequency when a new element enters the window and decrement when one leaves. Track a separate counter for how many numbers currently have non-zero frequency. Array indexing avoids hashing overhead and can be slightly faster in practice. Time complexity remains O(n), while space becomes O(R), where R is the value range. This technique works well when constraints guarantee small integers and fits typical array frequency counting patterns.
The key insight behind both methods is that consecutive windows overlap heavily. Instead of recalculating distinct counts from scratch, you update the state by removing the outgoing element and adding the incoming one. That transforms a naive O(nk) idea into a linear-time algorithm using a frequency structure from hash table techniques.
Recommended for interviews: Sliding Window with a hash table. It handles arbitrary values, scales to large inputs, and clearly demonstrates that you understand incremental window updates. Explaining the brute-force idea first shows problem understanding, but implementing the O(n) sliding window solution is what interviewers expect for this problem.
We use a hash table cnt to record the occurrence times of each number in the subarray of length k.
Next, we first traverse the first k elements of the array, record the occurrence times of each element, and after the traversal, we take the size of the hash table as the first element of the answer array.
Then, we continue to traverse the array from the index k. Each time we traverse, we increase the occurrence times of the current element by one, and decrease the occurrence times of the element on the left of the current element by one. If the occurrence times of the left element become 0 after subtraction, we remove it from the hash table. Then we take the size of the hash table as the next element of the answer array, and continue to traverse.
After the traversal, we return the answer array.
The time complexity is O(n), and the space complexity is O(k). Where n is the length of the array nums, and k is the parameter given by the problem.
Python
Java
C++
Go
TypeScript
We can also use an array to replace the hash table, which can improve performance to some extent.
The time complexity is O(n), and the space complexity is O(M). Where n is the length of the array nums, and M is the maximum value in the array nums. In this problem, M leq 10^5.
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window + Hash Table | — |
| Sliding Window + Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window + Hash Table | O(n) | O(k) | General case with arbitrary integer values; most common interview solution |
| Sliding Window + Array Frequency | O(n) | O(R) | When element values fall within a small known range and you want faster constant factors |
Leetcode 1852 | Distinct Numbers in Each Subarray | Sliding Window Technique • AverageLeeter • 803 views views
Watch 5 more video solutions →Practice Distinct Numbers in Each Subarray with our built-in code editor and test cases.
Practice on FleetCode