2799. Count Complete Subarrays in an Array

Problem Link

Description

---

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.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

 

Example 1:

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].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2000

Solution

---

Python3

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0
        complete = len(set(nums))
        counter = Counter()
        count = 0
        i = 0
        
        for j, x in enumerate(nums):
            if counter[x] == 0:
                count += 1
                
            counter[x] += 1
            
            while count == complete:
                counter[nums[i]] -= 1
                
                if counter[nums[i]] == 0:
                    count -= 1
                    
                i += 1
            
            res += i
                
        return res