Number of Subarrays with Bounded Maximum

Medium
797.

Number of Subarrays with Bounded Maximum

Number of Subarrays with Bounded Maximum is a medium coding problem on arrays, two pointers and sliding window, asked in Amazon, Google and Directi interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var numSubarrayBoundedMax = function(nums, left, right) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Subarrays with Bounded Maximum — Solution

Number of Subarrays with Bounded Maximum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Subarrays with Bounded Maximum is a medium coding problem on arrays, two pointers and sliding window, asked in Amazon, Google and Directi interviews.

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

Hints for Number of Subarrays with Bounded Maximum

  1. Hint 1

    'Maximum at most b' is much easier to count than 'maximum in a range'.

  2. Hint 2

    A subarray has maximum at most b exactly when every element is at most b — so it lies inside a maximal run of small elements.

  3. Hint 3

    count(max in [left, right]) = count(max ≤ right) − count(max ≤ left − 1).

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

  1. 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.
  2. 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)

Java

private static long countBoundedLE(int[] nums, long bound) {
    long res = 0, cur = 0;
    for (int x : nums) {
        if (x <= bound) {
            cur++;
            res += cur;
        } else {
            cur = 0;
        }
    }
    return res;
}

public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
    return (int) (countBoundedLE(nums, right) - countBoundedLE(nums, (long) left - 1));
}

C++

static long long countBoundedLE(vector<int>& nums, long long bound) {
    long long res = 0, cur = 0;
    for (int x : nums) {
        if (x <= bound) {
            cur++;
            res += cur;
        } else {
            cur = 0;
        }
    }
    return res;
}

int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    return (int) (countBoundedLE(nums, right) - countBoundedLE(nums, (long long) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique