Leetcode problem 111 - Count Complete Subarrays in an Array

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var countCompleteSubarrays = function (nums) {
  // Create a Set to get the distinct elements in the array
  const set = new Set(nums);

  // Get the size of the Set, representing the number of distinct elements in the entire array
  const setSize = set.size;

  // Create a Map to track the count of each element in the current subarray
  const map = new Map();

  // Initialize the variable to store the result (number of complete subarrays)
  let result = 0;

  // Initialize the left pointer for the sliding window
  let left = 0;

  // Initialize the variable to track the count of the current element in the subarray
  let count;

  // Iterate through each element in the array
  for (let i = 0; i < nums.length; ++i) {
    // Update the count of the current element in the Map
    map.set(nums[i], (map.get(nums[i]) || 0) + 1);

    // Check if the count of distinct elements in the current subarray is equal to the total distinct elements
    while (map.size === setSize) {
      // Increment the result by the number of subarrays ending at the current index
      result += nums.length - i;

      // Get the count of the element at the left pointer
      count = map.get(nums[left]);

      // Update the Map by either removing the element or decrementing its count
      if (count === 1) {
        map.delete(nums[left]);
      } else {
        map.set(nums[left], count - 1);
      }

      // Move the left pointer to the right
      ++left;
    }
  }

  // Return the final result (number of complete subarrays)
  return result;
};

The time complexity of this code is O(n), where n is the length of the input array nums. This is because the code uses a single loop that iterates through the array once.

The space complexity of this code is O(n), where n is the length of the input array nums. This is because the code uses a Set and a Map to store unique elements and their counts, respectively. The size of these data structures will grow with the number of unique elements in the array.