Skip to main content
Talentd

Number of Subarrays with Bounded Maximum - Solution & Explanation

MediumArrayTwo Pointers10 min readAsked at: Amazon, Adobe, Uber +1
Practice this problem

Problem Statement

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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= 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.

The function countSubarrays counts the number of subarrays where the maximum element is less than or equal to a given bound. By computing this for both the 'right' and 'left-1' bounds and subtracting the two results, we can find the count where the maximum element lies between 'left' and 'right'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array because we pass through the array twice both in O(n) time.
Space Complexity: O(1) as we only use a fixed amount of extra space.

Try this approach in the editor →

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), scanning and resolving limits in a single pass.
Space Complexity: O(1) maintaining concise storage need.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Consider Maximum Allowed Value

Time Complexity: O(n), where n is the length of the array because we pass through the array twice both in O(n) time.
Space Complexity: O(1) as we only use a fixed amount of extra space.

Sliding Window Technique

Time Complexity: O(n), scanning and resolving limits in a single pass.
Space Complexity: O(1) maintaining concise storage need.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Consider Maximum Allowed Value (count ≤ bound)O(n)O(1)Best general solution; simple linear pass using inclusion–exclusion
Sliding Window TechniqueO(n)O(1)When reasoning about window boundaries or practicing two-pointer patterns

Video Solution

Number Of Subarrays With Bounded Maximum | Leetcode 795 Solution in Hindi • Pepcoding • 12,246 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Number of Subarrays with Bounded Maximum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Subarrays With Median K

Next

Find the Number of Subarrays Where Boundary Elements Are Maximum