992. Subarrays with K Different Integers LeetCode Solution

In this guide, you will get 992. Subarrays with K Different Integers LeetCode Solution with the best time and space complexity. The solution to Subarrays with K Different Integers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Subarrays with K Different Integers solution in C++
Subarrays with K Different Integers solution in Java
Subarrays with K Different Integers solution in Python
Additional Resources

992. Subarrays with K Different Integers LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

992. Subarrays with K Different Integers LeetCode Solution in C++

class Solution {
 public:
  int subarraysWithKDistinct(vector<int>& nums, int k) {
    return subarraysWithAtMostKDistinct(nums, k) -
           subarraysWithAtMostKDistinct(nums, k - 1);
  }

 private:
  int subarraysWithAtMostKDistinct(const vector<int>& nums, int k) {
    int res = 0;
    vector<int> count(nums.size() + 1);

    for (int l = 0, r = 0; r < nums.size(); ++r) {
      if (++count[nums[r]] == 1)
        --k;
      while (k == -1)
        if (--count[nums[l++]] == 0)
          ++k;
      res += r - l + 1;  // nums[l..r], nums[l + 1..r], ..., nums[r]
    }

    return res;
  }
};
/* code provided by PROGIEZ */

992. Subarrays with K Different Integers LeetCode Solution in Java

class Solution {
  public int subarraysWithKDistinct(int[] nums, int k) {
    return subarraysWithAtMostKDistinct(nums, k) - subarraysWithAtMostKDistinct(nums, k - 1);
  }

  private int subarraysWithAtMostKDistinct(int[] nums, int k) {
    int res = 0;
    int[] count = new int[nums.length + 1];

    for (int l = 0, r = 0; r < nums.length; ++r) {
      if (++count[nums[r]] == 1)
        --k;
      while (k == -1)
        if (--count[nums[l++]] == 0)
          ++k;
      res += r - l + 1; // nums[l..r], nums[l + 1..r], ..., nums[r]
    }

    return res;
  }
}
// code provided by PROGIEZ

992. Subarrays with K Different Integers LeetCode Solution in Python

class Solution:
  def subarraysWithKDistinct(self, nums: list[int], k: int) -> int:
    def subarraysWithAtMostKDistinct(k: int) -> int:
      res = 0
      count = collections.Counter()

      l = 0
      for r, num in enumerate(nums):
        count[num] += 1
        if count[num] == 1:
          k -= 1
        while k < 0:
          count[nums[l]] -= 1
          if count[nums[l]] == 0:
            k += 1
          l += 1
        res += r - l + 1  # nums[l..r], nums[l + 1..r], ..., nums[r]

      return res

    return subarraysWithAtMostKDistinct(k) - subarraysWithAtMostKDistinct(k - 1)
 # code by PROGIEZ