Distinct Numbers in Each Subarray - Solution & Explanation
Problem Statement
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] <= 105
Approach Overview
Problem 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.
Approach 1: Sliding Window + Hash Table
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.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Sliding Window + Array
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.
Code
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window + Hash Table | — |
| Sliding Window + Array | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 1852 | Distinct Numbers in Each Subarray | Sliding Window Technique • AverageLeeter • 805 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Distinct Numbers in Each Subarray easy or hard?
Distinct Numbers in Each Subarray Python/Java solution
How to solve Distinct Numbers in Each Subarray in O(n)?
What is the best approach for Distinct Numbers in Each Subarray?
Is Distinct Numbers in Each Subarray asked at Google/Amazon/Meta?
What data structure is used in Distinct Numbers in Each Subarray?
What is the time complexity of Distinct Numbers in Each Subarray?
Ready to solve this problem?
Practice Distinct Numbers in Each Subarray with our built-in code editor and test cases.
Practice on FleetCode