Number of Subarrays with Bounded Maximum

Problem Description

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].

Key Insights

• A subarray is valid if its maximum element lies within the bounds defined by left and right.
• Use a two-pointer technique to efficiently count valid subarrays while traversing the nums array.
• Track boundaries where the maximum element is either too high or too low, allowing for counting valid segments.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we use a two-pointer approach to iterate through the array. We maintain a count of valid subarrays ending at each position. For each element:

1. If it is greater than right, reset the count since we can't include this element in any valid subarray.
2. If it is within the bounds of left and right, increase the count of valid subarrays.
3. If it is less than left, simply continue counting valid subarrays that end before this element.

This way, we accumulate the total number of valid subarrays in a single pass through the array.

Code Solutions