> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/sliding-window/subarray-at-most-problem.md).

# Sliding Window At Most Problem

## These problems are sliding windows but solve by 2 passes

[See Lee's posts](https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/523136/JavaC%2B%2BPython-Sliding-Window)

## 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`

```python
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 `0`s and `1`s, how many **non-empty** subarrays have sum `S`?

```python
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.

```python
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
```