Algorithm
Problem Name: 795. Number of Subarrays with Bounded Maximum
Problem Link: https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
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 <= 109
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
return countHelper(nums, right) - countHelper(nums, left - 1);
}
private int countHelper(int[] nums, int bound) {
int count = 0;
int curr = 0;
for (int num : nums) {
curr = num < = bound ? curr + 1 : 0;
count += curr;
}
return count;
}
}
Input
nums = [2,1,4,3], left = 2, right = 3
Output
3
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numSubarrayBoundedMax = function(A, L, R) {
let res = 0;
let j = 0;
let count = 0;
for(let i = 0; i < A.length; i++) {
if(A[i] >= L && A[i] <= R) {
res += i - j + 1
count = i - j + 1
} else if(A[i] < L> {
res += count
} else {
j = i + 1
count = 0
}
}
return res
};
Input
nums = [2,1,4,3], left = 2, right = 3
Output
3
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
res, start, diff = 0, -1, 0
for i in range (len(A)):
if L <= A[i] <= R: diff, res = i - start, res + i - start
elif A[i] > R: diff, start = 0, i
else: res += diff
return res
Input
nums = [2,9,2,5,6], left = 2, right = 8
Output
7