Count Subarrays With Fixed Bounds — Hard Problem & Solution

A subarray is fixed-bound when its minimum is exactly minK and its maximum is exactly maxK. Return the number of fixed-bound subarrays of nums.

Difficulty: Hard
Topics: Arrays, Two Pointers, Sliding Window, Queue
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A subarray is fixed-bound when its minimum is exactly minK and its maximum is exactly maxK.

Return the number of fixed-bound subarrays of nums.

Example 1

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: [1,3,5] and [1,3,5,2].

Example 2

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray qualifies.

Example 3

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 9
Output: 0
Explanation: No element equals 9.

Constraints

2 <= nums.length <= 50000
1 <= nums[i], minK, maxK <= 1000000

How to solve Count Subarrays With Fixed Bounds

For each right end, the set of valid left ends is an interval determined by three running positions. Counting its size at every step totals every valid subarray in one pass.

Approach

Track lastBad (the most recent element outside [minK, maxK]), lastMin and lastMax.
At index i, update whichever of the three applies.
The valid starts are lastBad + 1 … min(lastMin, lastMax); add min(lastMin, lastMax) - lastBad when positive.

Why it works

A subarray [l, i] is fixed-bound exactly when it avoids every out-of-range element (l > lastBad) and still reaches back to an occurrence of each bound (l <= lastMin and l <= lastMax). Those constraints define a contiguous range of l, whose size is the expression above — and it is 0 or negative precisely when no valid start exists.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Using >= instead of > against lastBad admits the out-of-range element itself.
minK may equal maxK, in which case both positions track the same index.
The count reaches about 1.25 · 10^9 at the stated size — accumulate carefully.

Reference solution

Python

from typing import List

def countSubarraysFixedBounds(nums: List[int], minK: int, maxK: int) -> int:
    res = 0
    last_min = last_max = last_bad = -1
    for i, x in enumerate(nums):
        if x < minK or x > maxK:
            last_bad = i
        if x == minK:
            last_min = i
        if x == maxK:
            last_max = i
        lo = min(last_min, last_max)
        if lo > last_bad:
            res += lo - last_bad
    return res

JavaScript

var countSubarraysFixedBounds = function(nums, minK, maxK) {
    var res = 0, lastMin = -1, lastMax = -1, lastBad = -1;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        if (x < minK || x > maxK) lastBad = i;
        if (x === minK) lastMin = i;
        if (x === maxK) lastMax = i;
        var lo = Math.min(lastMin, lastMax);
        if (lo > lastBad) res += lo - lastBad;
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue