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.lengthThe key idea for solving #992 Subarrays with K Different Integers is transforming the problem into counting subarrays with at most K distinct integers. Instead of directly counting subarrays with exactly K unique numbers, we compute the difference between the number of subarrays with atMost(K) distinct integers and atMost(K-1).
This is efficiently implemented using a sliding window combined with a hash table (or frequency map). The window expands with a right pointer while tracking element frequencies. If the number of distinct elements exceeds K, the left pointer shrinks the window until the constraint is satisfied again. For every valid window, we accumulate the number of subarrays ending at the current index.
This strategy avoids brute-force enumeration and ensures optimal performance. The sliding window processes each element at most twice, leading to a linear time complexity. The hash map stores counts of elements currently in the window, resulting in modest auxiliary space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Hash Map (atMostK technique) | O(n) | O(k) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Try generating all possible subarrays and check for the number of unique integers. Increment the count accordingly.
How about using a map to store the count of integers?
Think about the Sliding Window and 2-pointer approach.
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.
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.
1import java.util.HashMap;
2
3public class Solution {
4 public int subarraysWithKDistinct(int[] nums
This Java program makes use of two functions, subarraysWithKDistinct and atMost. The atMost function utilizes a HashMap to track the count of each number. It calculates the number of subarrays with at most k distinct numbers, which helps in finding the exact subarray count with k distinct integers by difference.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Counting subarrays with exactly K distinct elements directly is difficult. By calculating subarrays with at most K and subtracting those with at most K-1, we isolate the count of subarrays containing exactly K distinct integers.
Yes, variations of this problem frequently appear in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of sliding window techniques, hash maps, and counting strategies.
A hash map or frequency array is commonly used to track how many times each integer appears within the current sliding window. This structure allows quick updates when expanding or shrinking the window.
The optimal approach uses a sliding window with a hash map to count subarrays with at most K distinct integers. The final answer is obtained by subtracting the number of subarrays with at most K-1 distinct integers from those with at most K.