Algorithm
Problem Name: 992. Subarrays with K Different Integers
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]
has3
different integers:1
,2
, and3
.
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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int subarraysWithKDistinct(int[] A, int K) {
return atMostK(A, K) - atMostK(A, K - 1);
}
private int atMostK(int[] A, int K) {
int start = 0;
int end = 0;
int n = A.length;
Map map = new HashMap<>();
int count = 0;
while (end < n) {
if (map.getOrDefault(A[end], 0) == 0) {
K--;
}
map.put(A[end], map.getOrDefault(A[end], 0) + 1);
while (K < 0) {
map.put(A[start], map.getOrDefault(A[start], 0) - 1);
if (map.get(A[start]) == 0) {
K++;
}
start++;
}
count += end - start + 1;
end++;
}
return count;
}
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const subarraysWithKDistinct = function(A, K) {
let res = 0
let prefix = 0
const m = new Array(A.length + 1).fill(0)
for (let i = 0, j = 0, cnt = 0, len = A.length; i < len; i++) {
if (m[A[i]]++ === 0) cnt++
if (cnt > K) {
m[A[j++]]--
cnt--
prefix = 0
}
while (m[A[j]] > 1) {
prefix++
m[A[j++]]--
}
if (cnt === K) res += prefix + 1
}
return res
}
Copy The Code &
Try With Live Editor
Input
Output