
Problem Statement
You are provided with an integer array nums
alongside two integers, left
and right
. Your task is to calculate the number of contiguous subarrays where the maximum element within each subarray falls between left
and right
inclusive. This problem ensures that the resulting count can be accommodated within a 32-bit integer.
Examples
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 <= 105
0 <= nums[i] <= 109
0 <= left <= right <= 109
Approach and Intuition
Evaluating Subarrays
To tackle this problem, we can leverage two pointers technique or a sliding window approach to efficiently determine valid subarrays that meet the criteria.
Two Pointers Technique: This involves maintaining a
start
andend
pointer, initially both set to the start of the array.Expand
end
Pointer: Increase theend
pointer to explore new subarrays. For each position ofend
, you need to check if the current subarray (fromstart
toend
) contains a maximum value within the specified range[left, right]
.Adjust
start
Pointer: If the maximum value in the current subarray exceedsright
, move thestart
pointer rightwards until the max-value condition is satisfied again. This will help in excluding elements that push the subarray's maximum outside the desired range.Count Valid Subarrays: For each position of
end
that forms a valid subarray with the currentstart
, increment your count. The number of valid subarrays ending atend
with different starting points (start
) can be directly calculated if the maximum condition is satisfied.Optimal Data Structures: A deque (double-ended queue) can be used to efficiently keep track of the maximum of the current subarray. This optimizes finding the maximum value to a constant time operation, which is crucial given the constraint on the size of
nums
.
Example Walkthrough
Example 1:
- For the input
nums = [2,1,4,3]
withleft = 2
andright = 3
, the subarrays[2]
,[2, 1]
, and[3]
have their maximum values within[2, 3]
. - These subarrays are identified by expanding
end
and adjustingstart
to ensure the subarray's max falls within range.
- For the input
Example 2:
- Here,
nums = [2,9,2,5,6]
withleft = 2
andright = 8
. The approach involves identifying each subarray where the maximum falls between2
and8
. Due to the presence of9
which is outside the range, only certain segments of the array contribute to the count like[2]
,[2,9,2]
where segments get excluded when encountering9
.
- Here,
By utilizing an efficient subarray tracking method and maintaining a constant-time check on the maximum value, the problem can be addressed efficiently within the provided constraints.
Solutions
- Java
class Solution {
public int countSubarraysWithMaxWithinBounds(int[] nums, int low, int high) {
return helper(nums, high) - helper(nums, low - 1);
}
public int helper(int[] nums, int limit) {
int res = 0, count = 0;
for (int num : nums) {
count = num <= limit ? count + 1 : 0;
res += count;
}
return res;
}
}
The provided Java solution focuses on finding the count of subarrays within an array where the maximum value lies between two defined bounds, low
and high
.
- Utilize two function calls where each call efficiently calculates the cumulative count of all subarrays with maximum values less than or equal to a given limit.
- The main function,
countSubarraysWithMaxWithinBounds
, leverages the helper functionhelper
to achieve this by taking the difference between:- The count of subarrays with maximum values less than or equal to
high
. - The count of subarrays with maximum values less than
low - 1
(essentially the subarrays which don't meet the lower bound constraint).
- The count of subarrays with maximum values less than or equal to
The helper
function operates by iterating through each element of the array nums
and maintaining a running count (count
) of valid subarrays ending at each position that meet the condition specified by the 'limit' parameter. The result (res
) aggregates these valid counts across the entire array, being incremented continually by the value of count
at each step which resets whenever a number exceeds the limit. This efficient approach allows each element to be processed once, providing an overall time complexity of O(n), where n represents the number of elements in nums
.
No comments yet.