Intermediate Level
Implement the boundedMaximumSubarrayCount method that counts subarrays whose maximum value stays within a given range.
You are given an integer array and two boundary values left and right. Count how many continuous subarrays have a maximum element between left and right, inclusive.
A subarray is invalid if all its values are smaller than left, or if any value is greater than right.
Example 1
Input
nums (int[]) =
[2,1,4,3]size (int) =
4left (int) =
2right (int) =
3Returns (int)
3Example 2
Input
nums (int[]) =
[2,9,2,5,6]size (int) =
5left (int) =
2right (int) =
8Returns (int)
7Example 3
Input
nums (int[]) =
[1,1,1]size (int) =
3left (int) =
2right (int) =
3Returns (int)
0Scan the array and keep track of two positions: the last index where a value was greater than right, and the last index where a value was at least left.
For each index, any subarray ending there must start after the last too-large value. It is valid only if it includes at least one value inside the range. The number of valid subarrays ending at the current index is lastInRange - lastTooLarge.
Add this count for every index.
Pseudocode:
function boundedMaximumSubarrayCount(nums, size, left, right):
lastTooLarge = -1
lastInRange = -1
answer = 0
for i from 0 to size - 1:
if nums[i] > right:
lastTooLarge = i
if nums[i] >= left and nums[i] <= right:
lastInRange = i
if lastInRange > lastTooLarge:
answer += lastInRange - lastTooLarge
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run