Sponsored
Sponsored
To solve this problem, we iterate through the array and use two helper functions to find the number of subarrays with maximum elements less than or equal to `right` and strictly less than `left`. The result is the difference between these two values.
Time Complexity: O(n), where n is the length of the array because we pass through the array twice both in O(n) time.
Space Complexity: O(1) as we only use a fixed amount of extra space.
1#include <stdio.h>
2
3int countSubarrays(int* nums, int numsSize, int bound) {
4 int count = 0, result = 0, current = 0;
5 for (int i = 0; i < numsSize; i++) {
6 if (nums[i] <= bound) {
7 current++;
8 } else {
9 current = 0;
10 }
11 result += current;
12 }
13 return result;
14}
15
16int numSubarrayBoundedMax(int* nums, int numsSize, int left, int right) {
17 return countSubarrays(nums, numsSize, right) - countSubarrays(nums, numsSize, left - 1);
18}
19
20int main() {
21 int nums[] = {2, 1, 4, 3};
22 int left = 2, right = 3;
23 printf("%d\n", numSubarrayBoundedMax(nums, 4, left, right));
24 return 0;
25}The function countSubarrays counts the number of subarrays where the maximum element is less than or equal to a given bound. By computing this for both the 'right' and 'left-1' bounds and subtracting the two results, we can find the count where the maximum element lies between 'left' and 'right'.
This approach utilizes a sliding window to dynamically check and adjust the range within the array where subarrays satisfy the maximum constraints between `left` and `right`. We scan and adjust pointers to pinpoint valid ranges continuously.
Time Complexity: O(n), scanning and resolving limits in a single pass.
Space Complexity: O(1) maintaining concise storage need.
1def numSubarrayBoundedMax(nums, left, right):
2
The sliding window approach in Python for the specified problem uses a queue-like logic to maintain ranges that fall within the boundaries. Counter increments track the number of valid sequences built during iterations.