Watch 10 video solutions for Subarrays with K Different Integers, a hard level problem involving Array, Hash Table, Sliding Window. This walkthrough by NeetCodeIO has 27,663 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |