2537. Count the Number of Good Subarrays

Description

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: The only good subarray is the array nums itself.

Example 2:

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 109

 

Solutions

Solution: Sliding Window

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

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const countGood = function (nums, k) {
  const n = nums.length;
  const numMap = new Map();
  let left = 0;
  let pairs = 0;
  let result = 0;

  for (let index = 0; index < n; index++) {
    const num = nums[index];
    const count = numMap.get(num) ?? 0;

    pairs += count;
    numMap.set(num, count + 1);

    while (left < index && pairs >= k) {
      const leftNum = nums[left];
      const leftCount = numMap.get(leftNum);

      result += n - index;
      numMap.set(leftNum, leftCount - 1);
      pairs -= leftCount - 1;
      left += 1;
    }
  }

  return result;
};