Count Complete Subarrays in an Array

Intuition

Count Complete Subarrays in an Array - LeetCode::The number of elements to get upon each valid window = that window and all windows following that window.

Complexity

Runtime

• $O(N^2)$ brute force to generate each subarray
• $O(N)$ via sliding window approach

Space

$O(N)$ to get the set as well as counter (at most N elements)

Code

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        left = 0
        n = len(nums)
        global_count = len(set(nums))
        counter = Counter()
        count = 0
        for right in range(n):
            counter[nums[right]] += 1
            while left <= right and len(counter) == global_count:
                count += n - right
                
                counter[nums[left]] -= 1
                if counter[nums[left]] == 0:
                    del counter[nums[left]]
                left += 1
        return count

Notes

---

References

Count Complete Subarrays in an Array - LeetCode