Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/992.html
992. Subarrays with K Different Integers (Hard)
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
Example 1:
Input: A = [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: A = [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].
Note:
1 <= A.length <= 200001 <= A[i] <= A.length1 <= K <= A.length
Related Topics:
Hash Table, Two Pointers, Sliding Window
Similar Questions:
- Longest Substring Without Repeating Characters (Medium)
- Longest Substring with At Most Two Distinct Characters (Medium)
- Longest Substring with At Most K Distinct Characters (Hard)
Solution 1. Sliding Window
Use [i, j) as a sliding window to find the maximum window which contains no more than K unique elements.
To achieve this, we use a map m to store the last position of each number in the current window.
When m.size() > K, we should move forward i to shrink the window until it become valid again.
When m.size() == K, [i, j) is the maximum window we are looking for.
Within this maximum window [i, j), there is a minimum window [k, j) containing no more than K unique elements. k is the minimal index in m.
Now, the number of valid subarrays in this window is k - i + 1.
Since k is monotonically increasing and must be no less than i, we can use k as a global pointer just like i and j so that the overall time complexity of moving k is O(N).
Whenever m.size() == K, we can move k forward until m[A[k] - '0'] == k, and add k - i + 1 to the answer.
// OJ: https://leetcode.com/problems/subarrays-with-k-different-integers/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int subarraysWithKDistinct(vector<int>& A, int K) {
int ans = 0, i = 0, j = 0, k = 0, N = A.size();
unordered_map<int, int> m;
while (j < N) {
m[A[j] - '0'] = j;
++j;
while (m.size() > K) {
int d = A[i++] - '0';
if (m[d] < i) m.erase(d);
}
if (m.size() == K) {
k = max(i, k);
while (m[A[k] - '0'] != k) ++k;
ans += k - i + 1;
}
}
return ans;
}
};
-
class Solution { public int subarraysWithKDistinct(int[] A, int K) { if (A == null || A.length == 0 || K == 0) return 0; int subarrays = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int left = 0, right = 0; int length = A.length; while (right < length) { int rightNum = A[right]; int rightCount = map.getOrDefault(rightNum, 0) + 1; map.put(rightNum, rightCount); right++; while (map.size() > K) { int leftNum = A[left]; int leftCount = map.getOrDefault(leftNum, 0) - 1; if (leftCount > 0) map.put(leftNum, leftCount); else map.remove(leftNum); left++; } int pointer = left; while (map.size() == K) { subarrays++; int curNum = A[pointer]; int curCount = map.getOrDefault(curNum, 0) - 1; if (curCount > 0) map.put(curNum, curCount); else map.remove(curNum); pointer++; } pointer--; while (pointer >= left) { int curNum = A[pointer]; int curCount = map.getOrDefault(curNum, 0) + 1; map.put(curNum, curCount); pointer--; } } return subarrays; } } ############ class Solution { public int subarraysWithKDistinct(int[] nums, int k) { int[] left = f(nums, k); int[] right = f(nums, k - 1); int ans = 0; for (int i = 0; i < nums.length; ++i) { ans += right[i] - left[i]; } return ans; } private int[] f(int[] nums, int k) { int n = nums.length; int[] cnt = new int[n + 1]; int[] pos = new int[n]; int s = 0; for (int i = 0, j = 0; i < n; ++i) { if (++cnt[nums[i]] == 1) { ++s; } for (; s > k; ++j) { if (--cnt[nums[j]] == 0) { --s; } } pos[i] = j; } return pos; } } -
// OJ: https://leetcode.com/problems/subarrays-with-k-different-integers/ // Time: O(N) // Space: O(N) class Solution { public: int subarraysWithKDistinct(vector<int>& A, int K) { int ans = 0, i = 0, j = 0, k = 0, N = A.size(); unordered_map<int, int> m; while (j < N) { m[A[j] - '0'] = j; ++j; while (m.size() > K) { int d = A[i++] - '0'; if (m[d] < i) m.erase(d); } if (m.size() == K) { k = max(i, k); while (m[A[k] - '0'] != k) ++k; ans += k - i + 1; } } return ans; } }; -
# 992. Subarrays with K Different Integers # https://leetcode.com/problems/subarrays-with-k-different-integers/ class Solution: def subarraysWithKDistinct(self, nums: List[int], k: int) -> int: n = len(nums) left = prefix = res = distinct = 0 count = Counter() for right, x in enumerate(nums): if count[x] == 0: distinct += 1 count[x] += 1 if distinct > k: count[nums[left]] -= 1 left += 1 prefix = 0 distinct -= 1 while count[nums[left]] > 1: count[nums[left]] -= 1 prefix += 1 left += 1 if distinct == k: res += prefix + 1 return res -
func subarraysWithKDistinct(nums []int, k int) (ans int) { f := func(k int) []int { n := len(nums) pos := make([]int, n) cnt := make([]int, n+1) s, j := 0, 0 for i, x := range nums { cnt[x]++ if cnt[x] == 1 { s++ } for ; s > k; j++ { cnt[nums[j]]-- if cnt[nums[j]] == 0 { s-- } } pos[i] = j } return pos } left, right := f(k), f(k-1) for i := range left { ans += right[i] - left[i] } return }