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 <= 109Problem 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.
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'.
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.
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.
Python
JavaScript
Time Complexity: O(n), scanning and resolving limits in a single pass.
Space Complexity: O(1) maintaining concise storage need.
| Approach | Complexity |
|---|---|
| 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. |
| Sliding Window Technique | Time Complexity: O(n), scanning and resolving limits in a single pass. |
| Default Approach | — |
| 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 |
Number Of Subarrays With Bounded Maximum | Leetcode 795 Solution in Hindi • Pepcoding • 12,099 views views
Watch 9 more video solutions →Practice Number of Subarrays with Bounded Maximum with our built-in code editor and test cases.
Practice on FleetCode