A subarray has minimum minK and maximum maxK exactly when three conditions hold at once: it contains at least one occurrence of minK, it contains at least one occurrence of maxK, and no element falls outside the range [minK, maxK]. The first two conditions force the min and max to reach the required values; the third prevents the min from going lower or the max from going higher.

The third condition has a useful consequence. An element outside [minK, maxK] can never appear in a valid subarray, so each such element acts as a wall that splits the array into independent segments. Both approaches below rely on this: the brute force uses it to stop extending a subarray early, and the optimal solution uses it to bound how far left a valid subarray can start.

Key Constraints:

Intuition

Check every possible subarray. For each pair of indices (i, j) where i <= j, compute the minimum and maximum of the subarray nums[i..j] and compare them against minK and maxK.

Recomputing the min and max from scratch for every pair would cost O(n^3). Instead, fix the start i and extend the end j one element at a time, updating a running min and max. The running min only decreases and the running max only increases as the subarray grows, so once the min drops below minK or the max exceeds maxK, no further extension can become valid and the inner loop can stop. This keeps the work at O(n^2) overall.

Algorithm

Visualization and Code

The early break trims work in practice, but an array of all minK values with minK == maxK still forces the full quadratic scan. The next approach counts the valid subarrays ending at each index in O(1), reducing the whole problem to a single pass.

Intuition

Count subarrays by their right endpoint. Every subarray ends at exactly one index, so if we can compute, for each index i, how many valid subarrays end at i, summing those counts covers every subarray exactly once.

A subarray ending at i is valid under the same three conditions as before: it contains minK, it contains maxK, and it has no element outside [minK, maxK]. Three positions, maintained during a single left-to-right scan, determine all of this:

A subarray ending at i satisfies all three conditions exactly when its start s lies in the range lastBad < s <= min(lastMin, lastMax). Starting at or before min(lastMin, lastMax) puts the latest occurrence of both bounds inside the window. Starting after lastBad excludes every out-of-range element, because each one seen so far has an index of at most lastBad. The number of starts in that range is min(lastMin, lastMax) - lastBad, counted only when it is positive.

Initializing all three trackers to -1 handles the start of the scan without special cases. lastBad = -1 acts as a wall immediately before index 0, and until both bounds have appeared, min(lastMin, lastMax) is -1, which never exceeds lastBad, so the formula contributes nothing.

Algorithm

Visualization and Code