Given an integer array nums and an integer k, return the number of good subarrays of nums.
A good array is an array where the number of different integers in that array is exactly k.
[1,2,3,1,2] has 3 different integers: 1, 2, and 3.A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,1,2,3], k = 2 Output: 7 Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
Example 2:
Input: nums = [1,2,1,3,4], k = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i], k <= nums.lengthProblem Overview: Given an integer array nums and an integer k, count how many contiguous subarrays contain exactly k distinct integers. The challenge is efficiently tracking distinct values while expanding and shrinking a subarray window.
Approach 1: Brute Force with Frequency Map (O(n²) time, O(n) space)
Start a subarray at every index and extend it to the right while tracking frequencies of elements using a hash map. Each time you add a new element, update the map and check the number of distinct keys. If the map contains exactly k distinct integers, increment the result. If the count exceeds k, break early since extending further will only increase distinct elements. This method is straightforward and demonstrates the core requirement of counting distinct elements, but the nested iteration leads to O(n²) time in the worst case. The map storing frequencies requires O(n) space.
Approach 2: Sliding Window with Two-Pointer Technique (O(n) time, O(n) space)
The optimal solution uses a sliding window and the key observation that counting subarrays with exactly k distinct integers equals: atMost(k) - atMost(k-1). The helper function atMost(x) counts subarrays with at most x distinct elements.
Maintain two pointers (left and right) and a frequency map implemented with a hash table. Expand right while inserting elements into the map. If the number of distinct keys exceeds x, move left forward and decrease frequencies until the window becomes valid again. For each position of right, add right - left + 1 to the result because all subarrays ending at right and starting between left and right are valid.
Running atMost(k) and atMost(k-1) each takes linear time because every element enters and leaves the window at most once. The final answer is their difference. This approach relies on careful pointer movement and frequency updates but avoids redundant work, achieving O(n) time and O(n) space.
The technique combines array traversal with dynamic window resizing. Once you recognize the exactly K = atMost(K) - atMost(K-1) pattern, many “exactly K distinct” problems reduce to the same sliding window template.
Recommended for interviews: Interviewers expect the sliding window solution. The brute force approach shows you understand the requirement of counting distinct elements, but the atMost(k) trick demonstrates stronger algorithmic thinking and mastery of two-pointer window patterns.
The two-pointer technique can be employed with a sliding window approach to count subarrays with exactly k distinct numbers. The key idea is to maintain a window using two pointers that expand and shrink to keep track of the number of unique integers.
For this, we use the number of subarrays with at most k distinct numbers and at most (k-1) distinct numbers. The difference between these two values gives the number of subarrays with exactly k distinct integers.
This Python function calculates the number of subarrays with exactly k distinct integers. The function atMost(k) helps in calculating the number of subarrays with at most k distinct integers using a sliding window technique.
We then utilize this function to find the result by calculating atMost(k) - atMost(k - 1), which gives us the count of subarrays with exactly k distinct numbers.
Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the data structure at most twice.
Space Complexity: O(n), due to the storage used by the hash map.
| Approach | Complexity |
|---|---|
| Sliding Window with Two-Pointer Technique | Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the data structure at most twice. Space Complexity: O(n), due to the storage used by the hash map. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Map | O(n²) | O(n) | Small arrays or when first reasoning about the problem |
| Sliding Window using atMost(k) Trick | O(n) | O(n) | General case and expected interview solution |
Subarrays with K Different Integers - Leetcode 992 - Python • NeetCodeIO • 27,663 views views
Watch 9 more video solutions →Practice Subarrays with K Different Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor