Count Complete Subarrays in an Array

main.md

Question

Approach

First, I computed the number of distinct elements in the entire array. This gave me the target count that each "complete" subarray must satisfy.

Then, I used a sliding window approach: I moved the left and right pointers to track subarrays, using a hash map to count the frequency of elements in the current window. Each time the number of distinct elements in the window matched the total distinct count, I knew that all subarrays starting from the current left and ending anywhere from the right to the end would also be valid, so I counted them accordingly.

To simplify the problem even more, I actually iterated over all subarrays and used a set to track distinct elements within each subarray (acceptable since n ≤ 1000).

Implementation

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        total_distinct = len(set(nums))
        n = len(nums)
        count = 0
        
        for i in range(n):
            seen = set()
            for j in range(i, n):
                seen.add(nums[j])
                if len(seen) == total_distinct:
                    count += 1
        
        return count

Complexities

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