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.
- 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 <= 1000000 <= nums[i] <= 10000000000 <= left <= right <= 1000000000
Hints for Number of Subarrays with Bounded Maximum
Hint 1
'Maximum at most
b' is much easier to count than 'maximum in a range'.Hint 2
A subarray has maximum at most
bexactly when every element is at mostb— so it lies inside a maximal run of small elements.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
countLE(b): walk the array keepingcur, the length of the current run of elements at mostb; reset it to 0 at any larger element and addcurto 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
leftcan be 0, makingleft - 1negative;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^9at the upper size limit, so accumulate in 64-bit; withn <= 10^5the answer itself still exceedsintonly 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