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

Solution: Sliding Window

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const subarraysWithKDistinct = function (nums, k) {
  const n = nums.length;

  const subarraysWithMostDistinct = m => {
    const counts = new Array(n + 1).fill(0);
    let left = 0;
    let result = 0;

    for (let index = 0; index < n; index++) {
      const num = nums[index];

      counts[num] += 1;
      if (counts[num] === 1) m -= 1;

      while (m < 0) {
        counts[nums[left]] -= 1;
        if (!counts[nums[left]]) m += 1;

        left += 1;
      }
      result += index - left + 1;
    }
    return result;
  };

  return subarraysWithMostDistinct(k) - subarraysWithMostDistinct(k - 1);
};