Count Complete Subarrays in an Array

You are given an array nums consisting of positive integers. A subarray of an array is 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. For example, given nums = [1,3,1,2,2], the answer is 4 because the complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2]. As another example, nums = [5,5,5,5] should return 10 because the array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

## Naive Solution

The brute-force approach involves iterating through all possible subarrays and checking if each subarray is complete. A subarray is complete if the number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

```python
def count_complete_subarrays_naive(nums):
    n = len(nums)
    total_distinct = len(set(nums))
    count = 0
    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            distinct_subarray = len(set(subarray))
            if distinct_subarray == total_distinct:
                count += 1
    return count

Optimal Solution

We can use a sliding window approach to solve this problem more efficiently. The idea is to maintain a window and expand it until it becomes a complete subarray. Once we find a complete subarray, we shrink it from the left until it is no longer complete. The number of complete subarrays ending at the current right index is equal to the number of elements we removed from the left.

def count_complete_subarrays(nums):
    n = len(nums)
    total_distinct = len(set(nums))
    count = 0
    left = 0
    freq_map = {}
    distinct_count = 0

    for right in range(n):
        if nums[right] not in freq_map:
            freq_map[nums[right]] = 0
        if freq_map[nums[right]] == 0:
            distinct_count += 1
        freq_map[nums[right]] += 1

        while distinct_count == total_distinct:
            count += n - right
            freq_map[nums[left]] -= 1
            if freq_map[nums[left]] == 0:
                distinct_count -= 1
            left += 1

    return count

Big(O) Run-time Analysis

• Naive Solution: The naive solution has a time complexity of O(n^3), where n is the length of the input array. This is because we iterate through all possible subarrays (O(n^2)) and for each subarray, we count the number of distinct elements (O(n)).
• Optimal Solution: The optimal solution has a time complexity of O(n), where n is the length of the input array. This is because we use a sliding window that expands and shrinks at most n times.

Big(O) Space Usage Analysis

• Naive Solution: The naive solution has a space complexity of O(n), where n is the length of the input array. This is because we store the subarray in each iteration.
• Optimal Solution: The optimal solution has a space complexity of O(k), where k is the number of distinct elements in the input array. This is because we use a hash map to store the frequency of each element in the window.

Edge Cases

1. Empty Array: If the input array is empty, the number of complete subarrays is 0.
2. Array with One Element: If the input array has only one element, the number of complete subarrays is 1.
3. Array with All Same Elements: If the input array has all the same elements, any subarray is complete. The number of complete subarrays is n * (n + 1) / 2.
4. Array with All Distinct Elements: If the input array has all distinct elements, only the whole array is complete. The number of complete subarrays is 1 if the length of the array is greater than 0 and all elements are distinct.