Count Complete Subarrays in an Array — LeetCode 2799 Python Solution

The problem

You are given an array nums consisting of positive integers. We call a subarray of an array 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.

Example

Input

nums = [1,3,1,2,2]

Output

4

Explanation

The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Python solution

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        cnt = len(set(nums))
        ans, n = 0, len(nums)
        for i in range(n):
            s = set()
            for x in nums[i:]:
                s.add(x)
                if len(s) == cnt:
                    ans += 1
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2799. Count Complete Subarrays in an Array is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems