Count Subarrays With Fixed Bounds — Solution

Problem

Given an array of integers and two bounds minK and maxK, count how many subarrays have a minimum value of exactly minK and a maximum value of exactly maxK. Every element in such a subarray must fall within [minK, maxK], with the smallest element hitting minK exactly and the largest hitting maxK exactly.

• Input: nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5
• Output: 2
• Explanation: [1, 3, 5] and [1, 3, 5, 2] each have min = 1 and max = 5; the subarray [3, 5, 2] fails because its minimum is 2, not 1

Counter-example: [1, 3, 5, 2, 7, 5] — once index 4 (value 7) appears, any subarray containing it is automatically disqualified because 7 > maxK = 5.

Intuition

A valid subarray must include at least one minK and one maxK, and cannot contain any element outside [minK, maxK]. The key observation: for any right endpoint, the leftmost valid start is constrained by two things — it must come after the last out-of-range element (which breaks the window entirely), and it must be at or before the earlier of the last minK and last maxK positions (to guarantee both bounds are covered). Counting valid left starts is then a single arithmetic expression per element.

Solution — Tracked-Index Sliding Window

For each position right, maintain three indices: the last position of an out-of-range element, the last position of minK, and the last position of maxK. The number of valid subarrays ending at right is the count of valid left starting points, which lies in the range (bad_idx, min(last_min, last_max)].

1. Initialize bad_idx = -1, last_min = -1, last_max = -1, result = 0
2. For each index right, examine nums[right]:
3. If the value falls outside [minK, maxK], update bad_idx = right — this element cannot appear in any valid subarray
4. If the value equals minK, update last_min = right; if it equals maxK, update last_max = right
5. Add max(0, min(last_min, last_max) - bad_idx) to result — this counts valid left endpoints
6. Return result

1def countSubarrays(self, nums: list[int], minK: int, maxK: int) -> int:
2    result = 0
3    bad_idx = -1    # last position of a value outside [minK, maxK]
4    last_min = -1   # last position where the value equals minK
5    last_max = -1   # last position where the value equals maxK
6
7    for right, value in enumerate(nums):
8        if value < minK or value > maxK:
9            bad_idx = right  # any subarray spanning this index is disqualified
10        if value == minK:
11            last_min = right
12        if value == maxK:
13            last_max = right
14        # left boundary can start anywhere from bad_idx+1 to min(last_min, last_max)
15        # giving min(last_min, last_max) - bad_idx valid starting positions
16        result += max(0, min(last_min, last_max) - bad_idx)
17
18    return result

Time: O(n) — a single pass with O(1) work per element

Space: O(1) — only three index variables regardless of input size

Complexity Summary

Common Mistakes

• Misunderstanding what bad_idx resets: an out-of-range element does not just shrink the window from the left — it completely invalidates any subarray containing it. bad_idx must be updated to the element's position, not to bad_idx + 1.
• Off-by-one in the count formula: valid left starts run from bad_idx + 1 through min(last_min, last_max) inclusive, which is exactly min(last_min, last_max) - bad_idx positions. Subtracting bad_idx + 1 gives one fewer — a common error when converting the range to a count.
• Assuming uninitialized indices cause bugs: initializing last_min = last_max = bad_idx = -1 is intentional. When neither minK nor maxK has been seen yet, min(-1, -1) - (-1) = 0, so no subarrays are counted. The math self-corrects without special-casing.
• Forgetting long for the return type in Java/C++: the answer can reach O(n²) in magnitude — for nums = [minK, maxK, minK, maxK, ...] of length 10⁵, the count approaches 10¹⁰, overflowing a 32-bit integer.
• Missing the minK == maxK case: when both bounds are equal, the same element satisfies both if branches simultaneously, updating both last_min and last_max in a single step. The solution handles this correctly without special logic, but it's easy to accidentally add an else if that breaks it.

Related Problems

• sliding-window-maximum — tracks extreme values within a window using a deque, the structure that underlies many fixed-window problems
• minimum-window-substring — counts valid starting positions after satisfying character-frequency constraints, the same "count valid lefts" pattern
• max-consecutive-ones-iii — sliding window that tracks a disqualifying condition (too many zeros), analogous to bad_idx
• subarray-sum-equals-k — counting subarrays satisfying an exact numeric condition, different technique but same goal
• longest-repeating-character-replacement — sliding window with a two-sided constraint on what qualifies as a valid window