Why I Stopped Trying to Count "Exactly Right" and Started Subtracting

I've been working through coding problems that I can understand when reading solutions but struggle to solve on my own. This series is about breaking down the "why does this actually work" part. Not tutorials. Just honest breakdowns of where my thinking got stuck and what finally unstuck it.

The problem that broke my brain

LeetCode 795: Number of Subarrays with Bounded Maximum. You get an array of integers and a range [left, right]. Count how many contiguous subarrays have their maximum element within that range.

I understood what the problem was asking. I could verify answers by hand. But when I sat down to code it, I kept getting tangled. My sliding window logic was a mess because every element fell into one of three buckets: too small (below left), just right (in the range), or too big (above right). Each bucket needed different handling, and my code reflected that confusion.

Three zones, two problems

Here's what made this problem feel harder than it should be. When an element is bigger than right, it's a hard wall. No valid subarray can include it. You reset everything.

But when an element is smaller than left? It's fine. It just can't be the maximum. A subarray like [2, 1, 1] with left=2, right=3 is perfectly valid because the max is 2. The small elements are just passengers.

So "not in range" actually means two completely different things depending on which side you fall on. Trying to handle both cases in one pass meant tracking which elements were carrying the subarray (in-range elements) separately from which elements were just tagging along (too-small elements). Every if/else branch got another condition. The logic kept growing.

That's when I realized: maybe counting "exactly in range" directly is the wrong approach.

What if you only had one boundary?

Consider a simpler question: how many subarrays have their maximum ≤ some value k?

This is dramatically easier. There's only one type of violation. If an element is ≤ k, it extends your current valid window. If it's > k, the window breaks. Two states, one condition.

And here's the counting trick that makes it fast. At each position i, the number of valid subarrays ending at that position equals the current window length. If you've had 4 consecutive elements all ≤ k, there are exactly 4 subarrays ending at position 3: the single element, the pair ending here, the triple, and all four together.

def count_at_most(nums, k):
    run = total = 0
    for x in nums:
        run = run + 1 if x <= k else 0
        total += run
    return total

That's the entire helper. Walk through nums = [2, 1, 1, 3] with k = 3:

Position	Element	≤ 3?	Run	Subarrays ending here
0	2	yes	1	[2]
1	1	yes	2	[1], [2,1]
2	1	yes	3	[1], [1,1], [2,1,1]
3	3	yes	4	[3], [1,3], [1,1,3], [2,1,1,3]

Total: 1 + 2 + 3 + 4 = 10. Every subarray in the entire array has max ≤ 3.

The subtraction

Now the key move. "Max is in [left, right]" means "max ≤ right" AND "max ≥ left." That second condition is the annoying one. But you can rewrite it:

subarrays where max is in [left, right] = subarrays where max ≤ right minus subarrays where max ≤ left - 1

The first count includes everything up to right. The second count captures the ones that are too small (max below left). Subtracting removes exactly those.

Same array, left = 2, right = 3:

atMost(3) = 10 (computed above)

atMost(1):

Position	Element	≤ 1?	Run	Count
0	2	no	0	0
1	1	yes	1	1
2	1	yes	2	2
3	3	no	0	0

Total: 3.

Answer: 10 - 3 = 7. The valid subarrays are [2], [2,1], [2,1,1], [2,1,1,3], [1,1,3], [1,3], [3].

The full solution is five lines:

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def count_at_most(k):
            run = total = 0
            for x in nums:
                run = run + 1 if x <= k else 0
                total += run
            return total

        return count_at_most(right) - count_at_most(left - 1)

Where else this works (and where it doesn't)

This decomposition isn't specific to "bounded max." It works anywhere you need to count subarrays defined by a range, as long as the "at most" version behaves nicely with a sliding window.

LeetCode 992 (Subarrays with Exactly K Distinct Integers) is the same idea wearing different clothes. Counting "exactly K distinct" directly is painful because valid subarrays form a band in the middle of your window. Some shorter subarrays ending at the same position might have fewer than K distinct elements. Some longer ones might have more. You'd need two left pointers to track both edges of that band.

But "at most K distinct" is a clean sliding window. One left pointer, shrink when you exceed K. So: exactly(K) = atMost(K) - atMost(K - 1).

LeetCode 1248 (Count Number of Nice Subarrays) is the same pattern again, just counting odd numbers instead of distinct elements.

The pattern works because of a property called monotonicity: if a window satisfies "max ≤ k," every sub-window inside it also satisfies "max ≤ k." Same for "distinct count ≤ k." Shrinking the window from the left can never violate the property if it already holds.

This breaks for something like "median ≤ k." Removing an element from the left of a window can increase or decrease the median unpredictably. You can't maintain a valid window by just shrinking, so the sliding window approach falls apart, and the subtraction decomposition with it.

The general rule: if a range constraint is making your counting hard, check whether you can split it into two one-sided constraints. If each one-sided version has the monotonicity property (valid window implies all sub-windows are valid), the decomposition works.

Practice problems

In order of difficulty, all using this pattern:

1. LeetCode 713 (Subarray Product Less Than K): Single-sided, products instead of max. The "subarrays ending here = window size" insight is the same.
2. LeetCode 2110 (Number of Smooth Descent Periods): Run-length counting, almost identical to the count_at_most helper.
3. LeetCode 992 (Subarrays with Exactly K Distinct Integers): The classic atMost(K) - atMost(K-1). Needs a hashmap for frequencies.
4. LeetCode 1248 (Count Number of Nice Subarrays): Same decomposition, counting odd numbers.
5. LeetCode 2444 (Count Subarrays With Fixed Bounds): Harder. Two simultaneous constraints without the subtraction shortcut. Tests whether you can extend the thinking.