2799. Count Complete Subarrays in an Array

Description

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

• The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

 

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2000

 

Solutions

Solution: Sliding Window

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

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const countCompleteSubarrays = function (nums) {
  const n = nums.length;
  const distinctCount = new Set(nums).size;
  const numMap = new Map();
  let left = 0;
  let result = 0;

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

    numMap.set(num, count + 1);

    while (numMap.size === distinctCount) {
      const leftNum = nums[left];
      const leftCount = numMap.get(leftNum);

      result += n - index;

      if (leftCount === 1) {
        numMap.delete(leftNum);
      } else {
        numMap.set(leftNum, leftCount - 1);
      }

      left += 1;
    }
  }

  return result;
};