[Leetcode] 2799. Count Complete Subarrays in an Array

https://leetcode.com/problems/count-complete-subarrays-in-an-array/description/?envType=daily-question&envId=2025-04-24

initial

So there is a very obvious n^2 solution. Also v impt that when doing double for loop, instead of doing

for i in range(n):
## some logic
for j in range(i+1,n):
## that logic repeated

we can instead do

for i in range(n):
for j in range(i,n):
## that logic

that logic in this case is adding number to our set and seeign the length of set is same as length of set of the given nums list.

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

solution

I also thought of sliding window but i just couldnt figure out how to extend the valid subarray as our right pointer moves to the right. We can do that by

res += left_pointer

oK so lets start with some basic logic.
If right pointer ends on certain index and the subarray from left to right's set's length is equal to target nums set length (k), then we have found a valid subarray. We wanna find the min left pointer so that left to right subarray is invalid subarray. This is counter intuitive but once we find that i value, that means from 0 to i-1, we have found valid subarrays. So we add res +=i

Now the confusing part for me was so with example [1,3,1,2,2],
When we're at j=4, we have count={1:1, 2:2} which contains only 2 distinct elements (less than k=3), so this window does not have all the distinct elements. But why the fk should we add res+=i where i is 2?

This is cuz we extend the valid subarrays found earlier ([1,3,1,2] and [3,1,2]) with the new value (value 2 at j=4) that our right pointer is including into these subarrays. With this new value, we can form 2 more valid subarrays [1,3,1,2,2] and [3,1,2,2]. That is why we add res+=i to extend these valid subcases.

complexity

o(n) time
o(k) where k is # of distinct number