Welcome to Subscribe On Youtube

992. Subarrays with K Different Integers

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

Solutions

• Java
• C++
• Python
• Go

• 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;
      }
  }
  

• class Solution {
  public:
      int subarraysWithKDistinct(vector<int>& nums, int k) {
          vector<int> left = f(nums, k);
          vector<int> right = f(nums, k - 1);
          int ans = 0;
          for (int i = 0; i < nums.size(); ++i) {
              ans += right[i] - left[i];
          }
          return ans;
      }
  
      vector<int> f(vector<int>& nums, int k) {
          int n = nums.size();
          vector<int> pos(n);
          int cnt[n + 1];
          memset(cnt, 0, sizeof(cnt));
          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;
      }
  };
  

• class Solution:
      def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
          def f(k):
              pos = [0] * len(nums)
              cnt = Counter()
              j = 0
              for i, x in enumerate(nums):
                  cnt[x] += 1
                  while len(cnt) > k:
                      cnt[nums[j]] -= 1
                      if cnt[nums[j]] == 0:
                          cnt.pop(nums[j])
                      j += 1
                  pos[i] = j
              return pos
  
          return sum(a - b for a, b in zip(f(k - 1), f(k)))
  
  

• 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