Problem Description

You are given an array nums consisting of positive integers.

A subarray is considered complete if it contains all the distinct elements that appear in the entire array. In other words, if the original array has k distinct elements, then a complete subarray must also contain exactly those k distinct elements (though possibly in different quantities).

Your task is to count how many complete subarrays exist in the given array.

For example, if nums = [1, 3, 1, 2, 2], the distinct elements in the entire array are {1, 2, 3}, so there are 3 distinct elements. A subarray like [3, 1, 2] would be complete because it contains all 3 distinct elements. However, a subarray like [1, 3, 1] would not be complete because it only contains 2 distinct elements (1 and 3), missing element 2.

A subarray is defined as a contiguous, non-empty sequence of elements from the array.

The goal is to return the total number of complete subarrays.

Intuition

The key insight is that we need to find all subarrays that contain every distinct element from the original array. First, we need to know what our target is - how many distinct elements exist in the entire array? We can find this by converting the array to a set and checking its size, let's call this cnt.

Once we know we need cnt distinct elements in our subarray, we can check all possible subarrays. The natural approach is to consider every possible starting position i for a subarray. For each starting position, we can extend the subarray one element at a time by moving the ending position to the right.

As we extend the subarray from position i, we maintain a set s to track which distinct elements we've seen so far in the current subarray. Each time we include a new element, we add it to our set. The moment our set size reaches cnt, we know we have a complete subarray - it contains all the distinct elements from the original array.

An important observation: once a subarray starting at i and ending at some position j becomes complete (has all cnt distinct elements), extending it further to the right will still keep it complete. However, the solution counts each complete subarray individually, so we increment our answer for each valid ending position.

This leads to a straightforward enumeration strategy: for each starting position, we expand rightward and count how many complete subarrays we can form from that starting point. The sum across all starting positions gives us the total count.

Learn more about Sliding Window patterns.

Solution Approach

The implementation uses a hash table and enumeration strategy to solve this problem efficiently.

Step 1: Count distinct elements in the entire array

cnt = len(set(nums))

We convert the array to a set to get all unique elements, then take its length. This gives us the target number of distinct elements that a complete subarray must have.

Step 2: Initialize variables

ans, n = 0, len(nums)

• ans keeps track of the total count of complete subarrays
• n stores the length of the array for convenience

Step 3: Enumerate all possible subarrays

for i in range(n):
    s = set()
    for x in nums[i:]:
        s.add(x)
        if len(s) == cnt:
            ans += 1

For each starting position i:

1. Create an empty set s to track distinct elements in the current subarray
2. Iterate through elements starting from position i to the end of the array
3. For each element x:
   • Add it to the set s (duplicates are automatically handled by the set)
   • Check if len(s) == cnt - this means we have collected all distinct elements
   • If true, increment the answer counter by 1

The inner loop for x in nums[i:] effectively extends the subarray one element at a time from the starting position i. Each time we extend, we check if we've formed a complete subarray.

Time Complexity: O(n²) where n is the length of the array. We have two nested loops - the outer loop runs n times, and for each iteration, the inner loop can run up to n times.

Space Complexity: O(n) for storing the sets. In the worst case, the set s can contain all distinct elements from the array.

Example Walkthrough

Let's walk through the solution with nums = [1, 3, 1, 2, 2].

Step 1: Find the target number of distinct elements

• Convert array to set: {1, 2, 3}
• cnt = 3 (we need 3 distinct elements for a complete subarray)

Step 2: Enumerate subarrays starting from each position

Starting at index 0 (i = 0):

• Initialize empty set s = {}
• Process nums[0] = 1: Add to set → s = {1}, size = 1 < 3
• Process nums[1] = 3: Add to set → s = {1, 3}, size = 2 < 3
• Process nums[2] = 1: Add to set → s = {1, 3}, size = 2 < 3 (1 already exists)
• Process nums[3] = 2: Add to set → s = {1, 3, 2}, size = 3 = cnt → Found complete subarray [1,3,1,2], ans = 1
• Process nums[4] = 2: Add to set → s = {1, 3, 2}, size = 3 = cnt → Found complete subarray [1,3,1,2,2], ans = 2

Starting at index 1 (i = 1):

• Initialize empty set s = {}
• Process nums[1] = 3: Add to set → s = {3}, size = 1 < 3
• Process nums[2] = 1: Add to set → s = {3, 1}, size = 2 < 3
• Process nums[3] = 2: Add to set → s = {3, 1, 2}, size = 3 = cnt → Found complete subarray [3,1,2], ans = 3
• Process nums[4] = 2: Add to set → s = {3, 1, 2}, size = 3 = cnt → Found complete subarray [3,1,2,2], ans = 4

Starting at index 2 (i = 2):

• Initialize empty set s = {}
• Process nums[2] = 1: Add to set → s = {1}, size = 1 < 3
• Process nums[3] = 2: Add to set → s = {1, 2}, size = 2 < 3
• Process nums[4] = 2: Add to set → s = {1, 2}, size = 2 < 3 (2 already exists)
• End reached, no complete subarrays found

Starting at index 3 (i = 3):

• Initialize empty set s = {}
• Process nums[3] = 2: Add to set → s = {2}, size = 1 < 3
• Process nums[4] = 2: Add to set → s = {2}, size = 1 < 3
• End reached, no complete subarrays found

Starting at index 4 (i = 4):

• Initialize empty set s = {}
• Process nums[4] = 2: Add to set → s = {2}, size = 1 < 3
• End reached, no complete subarrays found

Final Answer: 4 complete subarrays

The complete subarrays found are:

1. [1, 3, 1, 2] (indices 0-3)
2. [1, 3, 1, 2, 2] (indices 0-4)
3. [3, 1, 2] (indices 1-3)
4. [3, 1, 2, 2] (indices 1-4)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) where n is the length of the input array nums.

The algorithm uses two nested loops:

• The outer loop runs n times (iterating through each starting position i)
• The inner loop iterates through the subarray from position i to the end of the array, which in the worst case is n - i iterations
• The total number of iterations is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2, which simplifies to O(n²)
• Within the inner loop, the set.add() operation takes O(1) average time
• The comparison len(s) == cnt takes O(1) time

Therefore, the overall time complexity is O(n²).

Space Complexity: O(k) where k is the number of distinct elements in nums.

The space usage comes from:

• The initial set creation set(nums) which stores all unique elements, requiring O(k) space
• The set s created in each iteration of the outer loop, which can contain at most k distinct elements
• The variable cnt stores a single integer: O(1)
• The variables ans and n each store single integers: O(1)

Since k ≤ n (the number of distinct elements cannot exceed the total number of elements), and the dominant space usage is O(k), the overall space complexity is O(k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding "Complete" Definition

Issue: A common mistake is thinking that once a subarray becomes complete (contains all distinct elements), we should stop extending it. This leads to undercounting.

Example: For nums = [1, 3, 1, 2, 2] with distinct elements {1, 2, 3}:

• Starting at index 0: [1, 3, 1, 2] is complete
• But [1, 3, 1, 2, 2] is also complete!

Wrong approach:

for i in range(n):
    s = set()
    for x in nums[i:]:
        s.add(x)
        if len(s) == cnt:
            ans += 1
            break  # WRONG: Breaking here misses other complete subarrays

Correct approach: Continue checking even after finding the first complete subarray from each starting position, as all extensions of a complete subarray are also complete.

Pitfall 2: Using Dictionary Instead of Set Inefficiently

Issue: Some might use a dictionary to count element frequencies unnecessarily when only distinct elements matter.

Inefficient approach:

for i in range(n):
    freq = {}
    for x in nums[i:]:
        freq[x] = freq.get(x, 0) + 1
        if len(freq) == cnt:  # This works but is overkill
            ans += 1

Better approach: Use a set since we only care about distinct elements, not their frequencies. Sets have better space efficiency and clearer intent.

Pitfall 3: Optimization Opportunity - Early Termination

Issue: The current solution continues checking subarrays even when it's impossible to form a complete subarray.

Enhancement:

for i in range(n):
    # If remaining elements can't possibly contain all distinct elements
    if n - i < cnt:
        break
  
    s = set()
    for j, x in enumerate(nums[i:], start=i):
        s.add(x)
        if len(s) == cnt:
            # Once complete, all further extensions are also complete
            ans += (n - j)
            break

This optimization recognizes that once we find the first complete subarray starting at position i, all its extensions are automatically complete, so we can add (n - j) to the answer and move to the next starting position.