Number of Subarrays with Bounded Maximum — Medium Problem & Solution

Count the contiguous non-empty subarrays whose maximum element lies in the inclusive range [left, right].

Difficulty: Medium
Topics: Arrays, Two Pointers, Sliding Window
Asked at: Amazon, Google, Directi
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

Count the contiguous non-empty subarrays whose maximum element lies in the inclusive range [left, right].

Example 1

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: [2], [2,1] and [3].

Example 2

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Example 3

Input: nums = [1,1,1], left = 2, right = 3
Output: 0
Explanation: No subarray reaches 2.

Constraints

1 <= nums.length <= 100000
0 <= nums[i] <= 1000000000
0 <= left <= right <= 1000000000

How to solve Number of Subarrays with Bounded Maximum

Split the range condition into a difference of two prefix conditions. Counting subarrays whose every element is at most b is a one-pass scan over maximal runs.

Approach

countLE(b): walk the array keeping cur, the length of the current run of elements at most b; reset it to 0 at any larger element and add cur to the total each step.
Return countLE(right) - countLE(left - 1).

Why it works

A run of length L contributes L(L+1)/2 subarrays, which is what adding cur at each position accumulates. Every subarray with maximum at most right either has maximum at most left - 1 or has it in [left, right], and the two cases are disjoint — so the subtraction isolates the wanted count.

Complexity

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

Pitfalls

left can be 0, making left - 1 negative; countLE(-1) must simply return 0, which it does since every element is non-negative.
Trying to slide a window on 'maximum in range' directly fails — that predicate is not monotone.
The count reaches about 5 · 10^9 at the upper size limit, so accumulate in 64-bit; with n <= 10^5 the answer itself still exceeds int only in theory — here it is bounded by the stated limits.

Reference solution

Python

from typing import List

def numSubarrayBoundedMax(nums: List[int], left: int, right: int) -> int:
    def count_le(bound: int) -> int:
        res = 0
        cur = 0
        for x in nums:
            if x <= bound:
                cur += 1
                res += cur
            else:
                cur = 0
        return res

    return count_le(right) - count_le(left - 1)

JavaScript

var numSubarrayBoundedMax = function(nums, left, right) {
    var countLE = function(bound) {
        var res = 0, cur = 0;
        for (var i = 0; i < nums.length; i++) {
            if (nums[i] <= bound) { cur++; res += cur; } else cur = 0;
        }
        return res;
    };
    return countLE(right) - countLE(left - 1);
};

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

All 667 arrays problems · the whole catalogue