Number of Subarrays with Bounded Maximum solution and explanation
Google
9 more videos on this problem
Number Of Subarrays With Bounded Maximum | Leetcode 795 Solution in HindiPepcoding · 32:15 · 12K views
Number of Subarrays with Bounded Maximum 🔥🔥| Leetcode June Challenge | Leetcode 795 | C++ | HindiAyushi Sharma · 11:30 · 4K views
Leetcode Contest 74 Problem 3 - Number of Subarrays with Bounded Maximumcode_report · 9:14 · 4K views
Number of Subarrays with Bounded Maximum | LeetCode 795 | Coders CampCoders Camp · 9:45 · 4K views
Number of Subarrays with Bounded Maximum | Leetcode 795 | Live coding sessionCoding Decoded · 18:16 · 3K views
LeetCode 795. Number of Subarrays with Bounded MaximumHappy Coding · 14:40 · 1K views
Leetcode - Number of Subarrays with Bounded Maximum (Python)Timothy H Chang · 10:05 · 1K views
LeetCode 795. Number of Subarrays with Bounded MaximumErik Gao · 9:43 · 663 views
LeetCode | 795. Number of Subarrays with Bounded Maximum | Sliding Window | Variable SizedCompl3x · 13:45 · 526 views
Number of Subarrays with Bounded Maximum | Binary Search | 795 LeetCode | LeetCode Explore | Day 17CodeWithSunny · 23:14 · 513 views
The problem
Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,1,4,3], left = 2, right = 3 Output: 3 Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Example 2:
Input: nums = [2,9,2,5,6], left = 2, right = 8 Output: 7
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= left <= right <= 109
Approach overview
Problem Overview: Given an integer array nums and two integers left and right, count the number of contiguous subarrays where the maximum element lies within the inclusive range [left, right]. The challenge is counting valid subarrays efficiently without checking every subarray explicitly.
Approach 1: Consider Maximum Allowed Value (O(n) time, O(1) space)
The key observation: instead of directly counting subarrays where the maximum is in [left, right], compute count(max ≤ right) and subtract count(max ≤ left-1). A helper function scans the array and counts all subarrays whose maximum value is ≤ a given bound. During the scan, maintain a running length of the current valid segment; each new valid element extends the number of possible subarrays ending at that index. When an element exceeds the bound, reset the counter. The final answer is count(right) - count(left - 1). This linear pass over the array avoids nested loops and handles large inputs efficiently.
Approach 2: Sliding Window Technique (O(n) time, O(1) space)
This method tracks valid windows using a two pointers style sliding window. Maintain two markers: the most recent index where a value exceeded right, and the most recent index where a value was within [left, right]. As you iterate, any element greater than right breaks the window and resets counting. If the element falls within the valid range, update the last valid index. The number of valid subarrays ending at the current index equals the distance between the current index and the last invalid index, constrained by whether a valid maximum exists. This approach keeps constant state while iterating once through the array.
Recommended for interviews: The maximum-allowed-value counting trick is what most interviewers expect. It shows you understand how to transform the problem using inclusion–exclusion (count(right) - count(left-1)). The sliding window interpretation demonstrates the same idea through pointer tracking and is useful if you are comfortable reasoning about dynamic window boundaries.
Approach 1: Consider Maximum Allowed Value
To solve this problem, we iterate through the array and use two helper functions to find the number of subarrays with maximum elements less than or equal to `right` and strictly less than `left`. The result is the difference between these two values.
def countSubarrays(nums, bound):
count = result = current = 0
for num in nums:
if num <= bound:
current += 1
else:
current = 0
result += current
return result
def numSubarrayBoundedMax(nums, left, right):
return countSubarrays(nums, right) - countSubarrays(nums, left - 1)
nums = [2, 1, 4, 3]
left = 2
right = 3
print(numSubarrayBoundedMax(nums, left, right))public class Solution {
private static int countSubarrays(int[] nums, int bound) {
int count = 0, result = 0, current = 0;
for (int num : nums) {
if (num <= bound) {
current++;
} else {
current = 0;
}
result += current;
}
return result;
}
public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
}
public static void main(String[] args) {
int[] nums = {2, 1, 4, 3};
int left = 2, right = 3;
System.out.println(numSubarrayBoundedMax(nums, left, right));
}
}#include <vector>
#include <iostream>
using namespace std;
int countSubarrays(vector<int>& nums, int bound) {
int count = 0, result = 0, current = 0;
for (int num : nums) {
if (num <= bound) {
current++;
} else {
current = 0;
}
result += current;
}
return result;
}
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
}
int main() {
vector<int> nums = {2, 1, 4, 3};
int left = 2, right = 3;
cout << numSubarrayBoundedMax(nums, left, right) << endl;
return 0;
}function countSubarrays(nums, bound) {
let count = 0, result = 0, current = 0;
for (let num of nums) {
if (num <= bound) {
current++;
} else {
current = 0;
}
result += current;
}
return result;
}
function numSubarrayBoundedMax(nums, left, right) {
return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
}
const nums = [2, 1, 4, 3];
const left = 2;
const right = 3;
console.log(numSubarrayBoundedMax(nums, left, right));#include <stdio.h>
int countSubarrays(int* nums, int numsSize, int bound) {
int count = 0, result = 0, current = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] <= bound) {
current++;
} else {
current = 0;
}
result += current;
}
return result;
}
int numSubarrayBoundedMax(int* nums, int numsSize, int left, int right) {
return countSubarrays(nums, numsSize, right) - countSubarrays(nums, numsSize, left - 1);
}
int main() {
int nums[] = {2, 1, 4, 3};
int left = 2, right = 3;
printf("%d\n", numSubarrayBoundedMax(nums, 4, left, right));
return 0;
}using System;
public class Solution {
private static int CountSubarrays(int[] nums, int bound) {
int count = 0, result = 0, current = 0;
foreach (int num in nums) {
if (num <= bound) {
current++;
} else {
current = 0;
}
result += current;
}
return result;
}
public static int NumSubarrayBoundedMax(int[] nums, int left, int right) {
return CountSubarrays(nums, right) - CountSubarrays(nums, left - 1);
}
public static void Main() {
int[] nums = {2, 1, 4, 3};
int left = 2, right = 3;
Console.WriteLine(NumSubarrayBoundedMax(nums, left, right));
}
}Using Python, the solution is composed of countSubarrays function to determine subarray counts in bounds. This solution follows a common pattern across implementations with linear complexity.
Time Complexity: O(n) due to traversing the list twice.
Space Complexity: O(1) for no significant extra storage.
Approach 2: Sliding Window Technique
This approach utilizes a sliding window to dynamically check and adjust the range within the array where subarrays satisfy the maximum constraints between `left` and `right`. We scan and adjust pointers to pinpoint valid ranges continuously.
def numSubarrayBoundedMax(nums, left, right):
def count(bound):
ans = 0
subarray_count = 0
for x in nums:
if x <= bound:
subarray_count += 1
else:
subarray_count = 0
ans += subarray_count
return ans
return count(right) - count(left - 1)
nums = [2, 1, 4, 3]
left = 2
right = 3
print(numSubarrayBoundedMax(nums, left, right))function numSubarrayBoundedMax(nums, left, right) {
const count = bound => {
let ans = 0, subarray_count = 0;
for (const num of nums) {
if (num <= bound) {
subarray_count += 1;
} else {
subarray_count = 0;
}
ans += subarray_count;
}
return ans;
};
return count(right) - count(left - 1);
}
const nums = [2, 1, 4, 3];
const left = 2;
const right = 3;
console.log(numSubarrayBoundedMax(nums, left, right));The sliding window approach in Python for the specified problem uses a queue-like logic to maintain ranges that fall within the boundaries. Counter increments track the number of valid sequences built during iterations.
Time Complexity: O(n), scanning and resolving limits in a single pass.
Space Complexity: O(1) maintaining concise storage need.
Approach 3: Default Approach
func numSubarrayBoundedMax(nums []int, left int, right int) int {
f := func(x int) (cnt int) {
t := 0
for _, v := range nums {
t++
if v > x {
t = 0
}
cnt += t
}
return
}
return f(right) - f(left-1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Consider Maximum Allowed Value | Time Complexity: O(n) due to traversing the list twice. |
| Sliding Window Technique | Time Complexity: O(n), scanning and resolving limits in a single pass. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Consider Maximum Allowed Value (count ≤ bound) | O(n) | O(1) | Best general solution; simple linear pass using inclusion–exclusion |
| Sliding Window Technique | O(n) | O(1) | When reasoning about window boundaries or practicing two-pointer patterns |
Frequently asked questions
Is Number of Subarrays with Bounded Maximum easy or hard?
The problem is rated Medium because the brute-force idea is simple but inefficient. Recognizing the transformation using count(max ≤ bound) requires deeper insight into subarray counting and inclusion–exclusion techniques.
Number of Subarrays with Bounded Maximum Python/Java solution
Python and Java implementations typically follow the same logic: implement a helper function that counts subarrays where the maximum value is ≤ a bound, then compute count(right) − count(left − 1). Both versions run in O(n) time and O(1) extra space.
How to solve Number of Subarrays with Bounded Maximum in O(n)?
Use a counting helper that tracks the number of subarrays where the maximum value is ≤ a given bound. When the current element is within the bound, extend the current valid segment and add its length to the result. When the element exceeds the bound, reset the segment length. The final result equals count(right) − count(left − 1).
What is the best approach for Number of Subarrays with Bounded Maximum?
The most efficient approach counts subarrays whose maximum value is ≤ a bound. Compute count(max ≤ right) and subtract count(max ≤ left − 1). Each count is calculated with a single linear scan, resulting in O(n) time and O(1) space. This transformation avoids checking every possible subarray.
Is Number of Subarrays with Bounded Maximum asked at Google/Amazon/Meta?
This problem represents a common array and sliding window counting pattern frequently seen in interviews at companies like Amazon, Google, and Meta. Interviewers use it to evaluate reasoning about subarrays, boundary conditions, and linear-time optimizations.
What data structure is used in Number of Subarrays with Bounded Maximum?
The solution primarily uses simple variables while iterating through an array. The algorithm relies on counting segments and two-pointer style reasoning rather than complex data structures, which keeps space usage constant.
What is the time complexity of Number of Subarrays with Bounded Maximum?
The optimal solution runs in O(n) time because the array is scanned once while maintaining a running count of valid segments. Space complexity is O(1) since only a few integer variables are stored during the scan.