MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Number of Subarrays with Bounded Maximum

Written By ## Number of Subarrays with Bounded Maximum Introduction

The Number of Subarrays with Bounded Maximum problem presents us with two values, left and right indicating a range. Our task is to design an algorithm that returns the number of contiguous non-empty subarrays such that the maximum array element of the subarray falls within the range. This problem can be simply solved by traversing the array, updating the counter along the way until we find an element greater than the right value which requires us to update our subarray starting value, update our number of valid subarrays with our current counter and reset the counter. This continues until we traverse the full array.

## Number of Subarrays with Bounded Maximum Problem

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

### Example Inputs and Outputs

#### Example 1

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3

#### Example 2

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

#### Example 3

Input: nums = [1,2,3,4,5], left = 2, right = 4
Output: 9

## Number of Subarrays with Bounded Maximum Solutions

To solve this problem, we iterate through the given array and maintain two important variables: count and valid_subarrays. We start by initializing both variables to 0. As we traverse the array, if we encounter an element greater than the right value, we update the starting point (subarray_start) to the current element's index and reset the count of valid subarrays to 0. On the other hand, if the current element falls within the range specified by left and right, we calculate the count of valid subarrays starting from the last starting point up to the current element and update (valid_subarrays) accordingly. We keep accumulating the count of valid subarrays in the count variable throughout the process. Finally, we return the count variable, which represents the total number of contiguous non-empty subarrays that fall within the range specified.

``````def numSubarrayBoundedMax(nums, left, right):
count = 0
subarray_start = -1
valid_subarrays = 0

for i in range(len(nums)):
if nums[i] > right:
subarray_start = i
valid_subarrays = 0

if left <= nums[i] <= right:
valid_subarrays = i - subarray_start

count += valid_subarrays

return count

# Driver code and test cases
nums1 = [2, 1, 4, 3]
left1 = 2
right1 = 3
# Expected output: 3
print(numSubarrayBoundedMax(nums1, left1, right1))

nums2 = [1, 2, 3, 4, 5]
left2 = 2
right2 = 4
# Expected output: 9
print(numSubarrayBoundedMax(nums2, left2, right2))

nums3 = [2, 9, 2, 5, 6]
left3 = 2
right3 = 8
# Expected output: 7
print(numSubarrayBoundedMax(nums3, left3, right3))``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), The time complexity is O(N), where N is the length of the input array 'nums'
• Space Complexity: O(1), as we use a constant amount of extra space.