We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Complete Subarrays in an Array

Difficulty: Medium

Problem Description

You are given an array nums consisting of positive integers. We call a subarray of an array complete if 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.

Key Insights

  • A subarray is defined as a contiguous non-empty portion of the array.
  • To determine if a subarray is complete, we need to track the number of distinct elements in both the subarray and the entire array.
  • The problem can be approached using a sliding window technique combined with a hash table to count distinct elements efficiently.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve the problem, we can use the sliding window technique. We will maintain a window that expands and contracts while counting distinct elements using a hash table (or dictionary). The basic steps are as follows:

  1. First, determine the total number of distinct elements in the entire array.
  2. Use two pointers to represent the current subarray. The left pointer starts at the beginning, and the right pointer expands the window by moving to the right.
  3. As we expand the right pointer, we will add elements to a hash table to track the count of distinct elements within the window.
  4. Whenever the number of distinct elements in our current window matches the total distinct elements, we count this subarray as complete and increment our count.
  5. Then we move the left pointer to try to find new complete subarrays by reducing the size of the window and checking again.

This approach allows us to efficiently count complete subarrays without having to check each possible subarray individually.

Code Solutions

def countCompleteSubarrays(nums):
    from collections import defaultdict

    total_distinct = len(set(nums))
    left = 0
    current_distinct = 0
    count = 0
    freq_map = defaultdict(int)

    for right in range(len(nums)):
        if freq_map[nums[right]] == 0:
            current_distinct += 1
        freq_map[nums[right]] += 1

        while current_distinct == total_distinct:
            count += len(nums) - right  # Count all subarrays from left to right
            freq_map[nums[left]] -= 1
            if freq_map[nums[left]] == 0:
                current_distinct -= 1
            left += 1

    return count
← Back to All Questions