Number of subarrays with bounded maximum
November 13, 2022
two-pointersProblem URL: Number of subarrays with bounded maximum
We will use two pointers for get the range. l
is the left side of our sliding window, and r is the right side of our sliding window. We increment the size of our window (we increment r
) if the encountered number is >= left. However, if the number is greater than right, we need to shrink the window to size 0, so we advance the left pointer to position i
.
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
l, r, res = -1, -1, 0
for i, num in enumerate(nums):
if num >= left: r = i
if num > right: l = i
res += r - l
return res
Time Complexity: O(n)
Space Complexity: O(1)