Description
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.
For example, [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 * 104 1 <= nums[i], k <= nums.length
Approach
Use the sliding window technique to find the number of subarrays with at most k distinct elements. The good array count is the difference between the count of subarrays with at most k distinct elements and the count of subarrays with at most k-1 distinct elements.
For example, given the array [1,2,1,2,3] and k = 2
-
The count of subarrays with at most 2(k) distinct elements is 12
[1], [1,2], [1,2,1], [1,2,1,2], [2], [2,1], [2,1,2], [1], [1,2], [2], [2,3], [3] -
The count of subarrays with at most 1(k-1) distinct element is 5
[1], [2], [1], [2], [3]
💁♂️ The count of good subarrays is 12 - 5 = 7
Solution
/**
* Counts the number of subarrays with at most k distinct elements.
* @param {number[]} nums - The array of numbers.
* @param {number} k - The maximum number of distinct elements.
* @return {number} - The number of subarrays.
*/
function countSubarraysWithAtMostKDistinct(nums, k) {
const elementCount = {}; // Dictionary to store the frequency of elements
let distinctCount = 0; // Number of distinct elements in the current window
let totalSubarrays = 0; // Total number of valid subarrays
for (let left = 0, right = 0; right < nums.length; right++) {
if (!elementCount[nums[right]]) {
distinctCount++; // Increase distinct count if the element is not in the dictionary
elementCount[nums[right]] = 0;
}
elementCount[nums[right]]++;
// Shrink the window from the left if distinct count exceeds k
while (distinctCount > k) {
elementCount[nums[left]]--;
if (elementCount[nums[left]] === 0) {
distinctCount--; // Decrease distinct count if the element count drops to zero
}
left++;
}
totalSubarrays += right - left + 1; // Add the number of valid subarrays ending at right
}
return totalSubarrays;
}
/**
* Counts the number of subarrays with exactly k distinct elements.
* @param {number[]} nums - The array of numbers.
* @param {number} k - The exact number of distinct elements.
* @return {number} - The number of subarrays.
*/
var subarraysWithKDistinct = function (nums, k) {
return (
countSubarraysWithAtMostKDistinct(nums, k) -
countSubarraysWithAtMostKDistinct(nums, k - 1)
);
};
Complexity Analysis
Time Complexity
The time complexity for this approach is O(n), where n is the length of the input array nums. Although there is a while loop inside the for loop, the while loop will execute at most n times in total, so each element is processed at most twice.
Space Complexity
The space complexity is O(n), where n is the length of the input array nums. The space used by the count dictionary is proportional to the number of distinct elements in the array.