Watch 10 video solutions for Number of Subarrays with Bounded Maximum, a medium level problem involving Array, Two Pointers. This walkthrough by Pepcoding has 12,099 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |