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 · Analysis

Maintain the number of bad days in [l,r]. Shrink until it is at most k, then add r-l+1: every start inside the repaired window is valid, and any earlier start is invalid. Return 0 for k < 0, which also makes exactly-k = atMost(k)-atMost(k-1) work for k=0. Time O(n), auxiliary space O(1); the answer can be quadratic in n.

03 · Solution

Reference solution

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

Longest Substring Without Repeating Characters