Sliding Window At Most Problem

These problems are sliding windows but solve by 2 passes

See Lee's posts

992. Subarrays with K different Integers

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A

def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
    return self.atMost(A, K) - self.atMost(A, K-1)

def atMost(self, A, K):
    i = 0
    record = collections.defaultdict(int)
    count = 0
    n = len(A)
    
    for j in range(n):
        if record[A[j]] == 0:
            K-=1
        record[A[j]] += 1
        
        while K < 0:
            record[A[i]] -=1
            if record[A[i]] == 0:
                K+=1
            i+=1
        count += j-i+1    
    return count

930. Binary Subarrays with Sum

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

def numSubarraysWithSum(self, A: List[int], S: int) -> int:
    return self.atMost(A, S) - self.atMost(A, S-1)

def atMost(self, A, S):
    # [0,0,0,0,0], 0
    if S < 0: return 0
    i = 0
    n = len(A)
    count = 0
    
    for j in range(n):
        S -= A[j]
        while S < 0:
            S += A[i] 
            i+=1
        count += j-i+1   
        
    return count

1248. Count Number of Nice Subarrays

Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

def numberOfSubarrays(self, nums: List[int], k: int) -> int:
    return self.atMost(nums, k) - self.atMost(nums, k-1)

def atMost(self, nums, k):
    i = 0
    count = 0
    
    for j in range(len(nums)):
        k -= 1 if nums[j]%2 else 0
        while k < 0:
            k += 1 if nums[i]%2 else 0
            i += 1
        count += j-i+1   
    return count