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. 1 <= A.length <= 20000
  2. 1 <= A[i] <= A.length
  3. 1 <= K <= A.length

Related Topics:
Hash Table, Two Pointers, Sliding Window

Similar Questions:

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
    }
    

All Problems

All Solutions