Problem of The Day: Count Complete Subarrays in an Array

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        distinct_elements = set(nums)
        num_of_distincts = len(distinct_elements)
        N = len(nums)
        res = 0
        for i in range(N):
            seen = set()
            for j in range(i, N):
                seen.add(nums[j])
                if len(seen) == num_of_distincts:
                    res += 1
                elif len(seen) > num_of_distincts:
                    break

        return res

Editorial

Approach: Sliding Window

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        res = 0
        cnt = {}
        n = len(nums)
        right = 0
        distinct = len(set(nums))
        for left in range(n):
            if left > 0:
                remove = nums[left - 1]
                cnt[remove] -= 1
                if cnt[remove] == 0:
                    cnt.pop(remove)
            while right < n and len(cnt) < distinct:
                add = nums[right]
                cnt[add] = cnt.get(add, 0) + 1
                right += 1
            if len(cnt) == distinct:
                res += n - right + 1
        return res