Skip to main content

Number of Subarrays with Bounded Maximum

Problem Statement​

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

The test cases are generated so that the answer will fit in a 32-bit integer.

Example​

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≤1051 \leq nums.length \leq 10^5
  • 0≤nums[i]≤1090 \leq nums[i] \leq 10^9
  • 0≤left≤right≤1090 \leq left \leq right \leq 10^9

Solution​

Intuition​

To solve this problem, we can use a sliding window approach. The idea is to maintain a window of subarrays whose maximum elements are within the given range [left, right]. We can keep track of the start and end of this window and count the number of valid subarrays.

Time Complexity and Space Complexity Analysis​

  • Time Complexity: The solution involves a single pass through the array, making the time complexity O(n)O(n).
  • Space Complexity: The space complexity is O(1)O(1) since we are using a constant amount of extra space.

Code​

C++​

class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int count = 0, start = -1, last = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > right) {
start = i;
}
if (nums[i] >= left) {
last = i;
}
count += last - start;
}
return count;
}
};

Java​

class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
int count = 0, start = -1, last = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > right) {
start = i;
}
if (nums[i] >= left) {
last = i;
}
count += last - start;
}
return count;
}
}

Python​

class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
count = 0
start = -1
last = -1
for i in range(len(nums)):
if nums[i] > right:
start = i
if nums[i] >= left:
last = i
count += last - start
return count