Problem Statement in English

You’re given an integer array nums of length n. A subarray is called complete if it contains all the distinct integers in nums.

Return the number of complete subarrays in nums.

Approach

This is a fairly straightforward sliding window problem.

First off, you need to know all the distinct integers in nums. You can do this by converting nums into a set.

Then, you can use a sliding window to find all the complete subarrays. Within that sliding window you need to keep track of the number of distinct integers in the current window. You can do this using a dictionary (or hashmap) to count the occurrences of each integer.

Solution in Python


class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        l = 0
        target = set(nums)
        LEN = len(nums)
        hm = {}
        res = 0

        for r in range(LEN):
            num = nums[r]
            hm[num] = hm.get(num, 0) + 1

            while len(hm) == len(target):
                res += LEN - r
                num = nums[l]
                hm[num] -= 1

                if not hm[num]:
                    del hm[num]
                l += 1

        return res

Complexity

  • Time: O(n)O(n)
    Since we are using a sliding window, we only need to iterate through the array once. The inner while loop will also run at most nn times, so the overall time complexity is O(n)O(n).

  • Space: O(n)O(n)
    Since we are using a hashmap to store the counts of each integer in the current window, the space complexity is O(n)O(n) in the worst case.

And we are done.