Count Subarrays With Fixed Bounds

1. Define the problem

Count Subarrays With Fixed Bounds

You are given an integer array nums and two integers minK and maxK. A fixed-bound subarray is a contiguous subarray of nums where the minimum value in that subarray is exactly minK, and the maximum value in that subarray is exactly maxK. Return the number of fixed-bound subarrays. Checking every subarray directly is too slow. Instead, scan once and, for every index, keep three running trackers: the last index where minK appeared, the last index where maxK appeared, and the last index of any value outside [minK, maxK] . A valid subarray ending at the current index must start after that last out-of-range index (or it would contain a forbidden value), and must reach back far enough to include both a minK and a maxK. The number of valid starting points for a subarray ending here is simply the distance from the last out-of-range index up to whichever of the min/max trackers is closer — every subarray whose left boundary sits in that stretch is valid.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums_i, minK, maxK ≤ 10⁶

Example

Inputnums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5

Output2

Explanation The fixed-bound subarrays are [1, 3, 5] and [1, 3, 5, 2].

2. Visualize the solution

One pass, tracking the last minK, last maxK, and last bad value

Statusscan

i=0, val=1=minK. lastMinIdx=0. lastMaxIdx=-1 (no maxK seen). count += max(0, min(0,-1) - (-1)) = max(0, 0) = 0. total=0.

What happens in this step

i = 0, value = 1
value == minK -> lastMinIdx = 0
lastMaxIdx = -1, lastInvalid = -1
count += max(0, min(0, -1) - (-1)) = max(0, -1 - (-1) = 0) = 0

total = 0

Step 1 of 5

Steps to visualize

At each index, if the value is outside [minK, maxK], update lastInvalid to this index — no valid subarray ending later can start at or before it.
If the value equals minK, update lastMinIdx; if it equals maxK, update lastMaxIdx.
The count of new valid subarrays ending here equals the smaller of lastMinIdx and lastMaxIdx, minus lastInvalid — but never less than zero.
Add that count to the running total at every index.
After the full scan, the total is the number of fixed-bound subarrays.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One pass, tracking the last minK, last maxK, and last bad value

Statusscan

i=0, val=1=minK. lastMinIdx=0. lastMaxIdx=-1 (no maxK seen). count += max(0, min(0,-1) - (-1)) = max(0, 0) = 0. total=0.

What happens in this step

i = 0, value = 1
value == minK -> lastMinIdx = 0
lastMaxIdx = -1, lastInvalid = -1
count += max(0, min(0, -1) - (-1)) = max(0, -1 - (-1) = 0) = 0

total = 0

Step 1 of 5

4. Solution

Solution

solution.tsTypeScript

function countSubarrays(nums, minK, maxK) {
  let count = 0;
  let lastMinIdx = -1;
  let lastMaxIdx = -1;
  let lastInvalidIdx = -1;

  for (let i = 0; i < nums.length; i++) {
    const value = nums[i];

    if (value < minK || value > maxK) {
      lastInvalidIdx = i;
    }
    if (value === minK) {
      lastMinIdx = i;
    }
    if (value === maxK) {
      lastMaxIdx = i;
    }

    count += Math.max(0, Math.min(lastMinIdx, lastMaxIdx) - lastInvalidIdx);
  }

  return count;
}

Time: O(n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5`	`2`	example from the docstring
`nums = [1, 1], minK = 1, maxK = 1`	`3`	smallest valid input, where minK equals maxK
`nums = [9, 9, 9], minK = 1, maxK = 5`	`0`	no value in range at all, so no subarray can ever qualify
`nums = [1, 1, 1], minK = 1, maxK = 1`	`6`	minK and maxK are the same value, so every subarray qualifies
`nums = [5, 1, 5, 1], minK = 1, maxK = 5`	`6`	minK and maxK alternate directly next to each other repeatedly
`nums = [1, 5, 100, 1, 5], minK = 1, maxK = 5`	`2`	a single out-of-range value that splits the array into two separate windows

Count Subarrays With Fixed Bounds