Skip to content

[leetcode] 992. Subarrays with K Different Integers

Published: at 12:26 AM (3 min read)

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

Approach

Use the sliding window technique to find the number of subarrays with at most k distinct elements. The good array count is the difference between the count of subarrays with at most k distinct elements and the count of subarrays with at most k-1 distinct elements.

For example, given the array [1,2,1,2,3] and k = 2

  1. The count of subarrays with at most 2(k) distinct elements is 12

    [1], [1,2], [1,2,1], [1,2,1,2], [2], [2,1], [2,1,2], [1], [1,2], [2], [2,3], [3]

  2. The count of subarrays with at most 1(k-1) distinct element is 5

    [1], [2], [1], [2], [3]

💁‍♂️ The count of good subarrays is 12 - 5 = 7

Solution

/**
 * Counts the number of subarrays with at most k distinct elements.
 * @param {number[]} nums - The array of numbers.
 * @param {number} k - The maximum number of distinct elements.
 * @return {number} - The number of subarrays.
 */
function countSubarraysWithAtMostKDistinct(nums, k) {
  const elementCount = {}; // Dictionary to store the frequency of elements
  let distinctCount = 0; // Number of distinct elements in the current window
  let totalSubarrays = 0; // Total number of valid subarrays

  for (let left = 0, right = 0; right < nums.length; right++) {
    if (!elementCount[nums[right]]) {
      distinctCount++; // Increase distinct count if the element is not in the dictionary
      elementCount[nums[right]] = 0;
    }
    elementCount[nums[right]]++;

    // Shrink the window from the left if distinct count exceeds k
    while (distinctCount > k) {
      elementCount[nums[left]]--;
      if (elementCount[nums[left]] === 0) {
        distinctCount--; // Decrease distinct count if the element count drops to zero
      }
      left++;
    }
    totalSubarrays += right - left + 1; // Add the number of valid subarrays ending at right
  }
  return totalSubarrays;
}

/**
 * Counts the number of subarrays with exactly k distinct elements.
 * @param {number[]} nums - The array of numbers.
 * @param {number} k - The exact number of distinct elements.
 * @return {number} - The number of subarrays.
 */
var subarraysWithKDistinct = function (nums, k) {
  return (
    countSubarraysWithAtMostKDistinct(nums, k) -
    countSubarraysWithAtMostKDistinct(nums, k - 1)
  );
};

Complexity Analysis

Time Complexity

The time complexity for this approach is O(n), where n is the length of the input array nums. Although there is a while loop inside the for loop, the while loop will execute at most n times in total, so each element is processed at most twice.

Space Complexity

The space complexity is O(n), where n is the length of the input array nums. The space used by the count dictionary is proportional to the number of distinct elements in the array.