Counting Subarrays: atMost(k) − atMost(k−1)

Sometimes the question isn't "how long is the best window?" but "how many subarrays are valid?" Listing them is $O(n^2)$. A sliding window can count them in $O(n)$ thanks to one observation, covered first below. A second trick then turns hard "exactly k" counts into two easy "at most k" counts.

The idea#

Counting problems ask how many subarrays are valid, not which one is best. The sliding window still works, with two small changes to how you read the answer.

Every window adds its length#

Suppose the rule is monotonic: if a window is valid, every shorter window inside it is valid too ("product less than k", "at most k distinct"). After shrinking, start..end is the longest valid window ending at end. Then every subarray that ends at end and starts anywhere in start..end is valid as well:

• [start..end], [start+1..end], ..., [end..end]

That's end - start + 1 subarrays, and no other valid subarray ends at end. So the number of new subarrays is the length of the window itself. Add it at every step and you count each valid subarray exactly once, grouped by where it ends.

Exactly k = atMost(k) - atMost(k - 1)#

The first trick needs a monotonic rule, and "exactly k distinct" is not monotonic: a window with exactly k distinct can contain shorter windows with fewer. The window can be valid at several sizes for the same end, and counting them all directly without double counting is awkward. "At most k" is monotonic, so it's easy. Then subtract:

It's a set difference, like "numbers ≤ 10" minus "numbers ≤ 9" leaves only {10}.

How to spot it#

The question asks for a count, not a length. Look for these signals.

• "Return the number of (contiguous) subarrays such that ...".
• The rule is "at most" / "less than", or can be rewritten that way.
• "Exactly k" of something (distinct values, odd numbers, ones) where the "at most" version is a standard window.

Template#

The loop is the longest valid window loop. Only the last line changes: you add the window length instead of taking a max.

at_most(k):
    state = empty                     # count map, product, odd count
    start = 0
    total = 0
    for end in range(len(items)):
        add items[end] to state
        while state breaks the "at most k" rule:
            remove items[start] from state
            start += 1
        total += end - start + 1      # all valid subarrays ending here
    return total

exactly(k) = at_most(k) - at_most(k - 1)

Each pointer moves at most n times, so one call is $O(n)$ and the subtraction costs two passes.

Trace#

To see both tricks together, here is the trace for nums = [1, 2, 1, 2, 3] and "exactly 2 distinct". Each row adds the window length for at_most(2) and at_most(1).

So exactly 2 distinct is 12 - 5 = 7: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2] and [1,2,1,2].

Pitfalls#

Each of these mistakes quietly breaks the count.

• A shrink loop that never stops. If even the empty window breaks the rule, start runs past end and reads elements outside the window. Guard against that case before the loop.
• Adding the count before shrinking. The window must be valid when you add its length. Add after the while loop.
• Assuming any "exactly" fits. The subtraction is only as good as the at_most helper. It needs a rule where "valid" is closed under shrinking.
• at_most(0). It should return 0. In the template the while loop empties the window, so each step adds end - (end + 1) + 1 = 0.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

• 713. Subarray Product Less Than K
• 1248. Count Number of Nice Subarrays
• 992. Subarrays with K Different Integers

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• With a monotonic rule, the valid subarrays ending at end number exactly end - start + 1.
• Sum the window length at every step to count in $O(n)$.
• "Exactly k" is hard to window directly; "at most k" is easy.
• exactly(k) = at_most(k) - at_most(k - 1), a set difference.