Algorithm

Problem Name: 992. Subarrays with K Different Integers

Problem Link: https://leetcode.com/problems/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] 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

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

x
–
+
cmd
nums = [1,2,1,2,3], k = 2

Output

x
–
+
cmd
7

#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

x
–
+
cmd
nums = [1,2,1,2,3], k = 2

Output

x
–
+
cmd
7

Demonstration

Previous
#991 Leetcode Broken Calculator Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#993 Leetcode Cousins in Binary Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode