Counting subarrays: the at-most-K trick
In one line
Counting subarrays with exactly K of something is hard to do with one window, but counting 'at most K' is easy, so compute exactly(K) = atMost(K) - atMost(K - 1).
What it is
Some problems ask how many subarrays have a property, such as exactly K distinct values or exactly K odd numbers. A single sliding window struggles here, because for a fixed right end the valid left ends for 'exactly K' form a range in the middle, not a simple prefix you can track with one pointer.
'At most K' is different: if the window left..right is valid, every shorter window ending at right is valid too. So for each right, the number of valid subarrays ending there is right - left + 1. Summing that gives atMost(K) in O(n). Subarrays with exactly K are those with at most K minus those with at most K - 1.
Why interviewers ask
It shows up in hard problems like Subarrays with K Different Integers (LeetCode 992) and in mediums like Count Number of Nice Subarrays and Binary Subarrays With Sum. Interviewers like it because it tests counting skills (why right - left + 1), set reasoning (why the subtraction is exact) and the ability to reduce a hard question to an easier one, which is a valuable general habit.
How it works
- 1Write a helper atMost(K) using a variable window: grow right, update the state (count map, number of odds, running sum).
- 2While the window breaks the 'at most K' rule, remove nums[left] and move left forward.
- 3Now every subarray that ends at right and starts anywhere from left to right is valid. There are right - left + 1 of them; add that to the total.
- 4Return the total. Each subarray is counted exactly once, under its right end.
- 5Answer: exactly(K) = atMost(K) - atMost(K - 1). Every subarray with at most K is either exactly K or at most K - 1, never both, so the subtraction leaves exactly the K ones.
- 6The rule must be monotonic (a smaller window cannot have more of the thing): distinct counts, counts of odd numbers, sums of non-negative numbers.
Worked example · Subarrays of [1, 2, 1, 2, 3] with exactly 2 distinct values
- atMost(2): right = 0, window [1], add 1 (total 1). right = 1, [1, 2], add 2 (total 3). right = 2, [1, 2, 1], add 3 (total 6). right = 3, [1, 2, 1, 2], add 4 (total 10).
- right = 4 adds 3: three distinct, so shrink. Remove 1 (idx 0), still 3 distinct; remove 2 (idx 1), still 3; remove 1 (idx 2), now {2, 3}. left = 3, add 4 - 3 + 1 = 2 (total 12).
- atMost(1): each step the window shrinks to a single value or a run of equal values; here no two neighbours are equal, so each right adds 1. Total 5.
- exactly(2) = 12 - 5 = 7. Check by listing: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]: 7 subarrays.
Picture it
To count students who scored exactly 80, you can count everyone who scored at most 80 and subtract everyone who scored at most 79. Two easy 'at most' counts give you the hard 'exactly' count.
Reference code
from collections import defaultdict
def at_most_k_distinct(nums, k):
"""Number of subarrays with at most k distinct values."""
count = defaultdict(int)
left = distinct = total = 0
for right, x in enumerate(nums):
if count[x] == 0:
distinct += 1
count[x] += 1
while distinct > k: # shrink until valid again
count[nums[left]] -= 1
if count[nums[left]] == 0:
distinct -= 1
left += 1
total += right - left + 1 # valid subarrays ending at right
return total
def exactly_k_distinct(nums, k):
return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)
at_most_k_distinct counts all subarrays ending at each right in one step with right - left + 1. Two linear passes give the exact count: O(n) time, O(distinct values) space. With k = 0 the helper returns 0, which makes exactly_k_distinct(nums, 1) correct.
Key patterns
Exactly K distinct
When: Subarrays with K different integers (LeetCode 992)
How: atMost(K) - atMost(K - 1) with a count map and a distinct counter.
Exactly K odd numbers
When: Count number of nice subarrays (LeetCode 1248)
How: Treat odd as 1 and even as 0, then count subarrays with at most K ones, twice, and subtract.
Binary subarrays with sum S
When: 0/1 array, count subarrays summing to S (LeetCode 930)
How: atMost(S) - atMost(S - 1); handle S = 0 so that atMost(-1) returns 0. Prefix sums with a hash map also work.
Direct at-most count
When: Subarrays with product less than k (positive numbers, LeetCode 713)
How: Only one window needed: shrink while product >= k, add right - left + 1.
Real-world use
Analytics on event streams
Product analytics teams count sessions or time ranges where users touched exactly K different features; counting 'at most K' with a window and subtracting avoids enumerating every range.
Cumulative counts in databases and reports
Cumulative counts are a standard way to get exact counts: 'how many rows have value = K' equals cumulative(<= K) minus cumulative(<= K - 1), the same idea databases and histograms use with cumulative distributions.
Genome and text statistics
Bioinformatics and NLP tools count substrings with a bounded number of distinct symbols or mismatches, which is an at-most-K window count over a sequence.
Quality monitoring
Manufacturing and SRE reports count time ranges containing exactly K faults or errors, computed as ranges with at most K minus ranges with at most K - 1.
In a project
A learning platform wants to report, for each course, how many contiguous stretches of a student's activity log contain exactly 3 different modules, as a measure of focused versus scattered study.
- Map each activity event to its module id, giving an array per student.
- Write atMost(K) with a count map: grow the window, shrink while more than K modules are present, and add right - left + 1 per step.
- Compute exactly(3) = atMost(3) - atMost(2) for each student and aggregate per course.
- Validate on a few short logs against a brute-force O(n^2) counter in unit tests.
Impact: The report runs in O(n) per student instead of O(n^2), so it handles logs with tens of thousands of events in the nightly job, and the unit tests prove the counting is exact.
Trade-offs
Use it when
- The question counts subarrays with exactly K of something
- 'At most K' is monotonic: shrinking a valid window keeps it valid
- Values are non-negative or the property is a count (distinct, odd, ones)
Avoid it when
- Sums with negative numbers: use prefix sums with a hash map of counts (Subarray Sum Equals K)
- You need the subarrays themselves, not just how many: there can be O(n^2) of them
- The property is not monotonic in window size
Cost: Time O(n) per atMost call, so O(n) overall. Space O(1) for counts of odds or sums, O(distinct values) for a count map.
Common mistakes
- Trying to count 'exactly K' with a single window and missing subarrays whose left end is not the current left.
- Adding 1 per step instead of right - left + 1, which counts windows instead of subarrays.
- Using the trick on sums with negative numbers, where the window logic is not valid.
- Not handling K = 0 so that atMost(-1) breaks; it should return 0.
- Forgetting that answers can be large: up to n(n+1)/2 subarrays.
Interview questions
Quick revision
- exactly(K) = atMost(K) - atMost(K - 1).
- In atMost: after shrinking, add right - left + 1 subarrays.
- Requires monotonic property (counts, non-negative sums).
- Total subarrays in an array of n: n(n+1)/2.
- Negative numbers + exact sum: prefix sums + hash map instead.
- atMost(-1) must return 0.
- Time O(n), space O(distinct values).
Check yourself
1. How many subarrays does an array of length 4 have in total?
2. In the atMost helper, the window after shrinking is left = 2, right = 5. How many valid subarrays end at index 5?
3. Which problem should NOT use the at-most-K window trick?
4. For nums = [1, 1, 1] and K = 1 distinct value, what is exactly(1)?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.