Solution: Count Subarrays With Fixed Bounds

Statement

Given an integer array, nums, and two integers minK and maxK, return the number of fixed-bound subarrays.

A subarray in nums is called a fixed-bound subarray if it satisfies the following conditions:

1. The smallest value in the subarray equals minK.

2. The largest value in the subarray equals maxK.

Note: A subarray is a contiguous sequence of elements within an array.

Constraints:

• $2 \leq$ nums.length $\leq 10^{3}$

• $1 \leq$ nums[i], minK, maxK $\leq 10^{3}$

Solution

A brute-force approach of checking every subarray to see if it contains minK and maxK would be too slow, so instead, we take a more efficient, single-pass strategy. Moving through the array from left to right, we keep track of just enough information to determine the count of all the valid fixed-bound subarrays.

A subarray is only valid (fixed-bound) if it includes both minK and maxK, and contains no invalid numbers (i.e., numbers outside the range [minK, maxK]. So, to identify valid subarrays ending at a certain position in the list, we focus on three important markers:

• The one where we last saw minK.

• The one where we last saw maxK

• The one where we last saw a number outside the range [minK, maxK].

While iterating over nums, we check whether we have seen both minK and maxK at each step. If we have, we look at the earlier of those two positions. This tells us the furthest back we can go while including both required values. But we also need to ensure the subarray doesn't include invalid numbers, so we compare this earliest position with the last invalid index.

Suppose the last invalid number appeared before the minK and maxK positions earlier. In that case, all subarrays that start after that invalid position and end at the current index will be valid. The number of such valid subarrays is simply the possible starting points between the index after the last invalid element and the earlier of the two bound positions (inclusive). Each start point gives one valid subarray ending at the current index. We accumulate that count as we go.