Count Subarrays with At Most K Bad Days

01 · Question

Counting Subarrays (At-Most-K)

Given an array of sales, count the number of subarrays with at most k bad days (days with fewer than 10 sales).

Key Insight: If a window [l, r] is valid (has <= k bad days), then all subarrays ending at r within this window (i.e., starting from l, l+1, ..., r) are also valid. There are r - l + 1 such subarrays.

02 · Solution

Reference solution

1def count_at_most_k_bad_days(sales: List[int], k: int) -> int:
2    l = 0
3    count = 0
4    bad_days = 0
5    
6    for r in range(len(sales)):
7        if sales[r] < 10:
8            bad_days += 1
9        
10        while bad_days > k:
11            if sales[l] < 10:
12                bad_days -= 1
13            l += 1
14            
15        count += (r - l + 1)
16        
17    return count

Longest Substring Without Repeating Characters