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 <vector>
2#include <iostream>
3using namespace std;
4
5int countSubarrays(vector<int>& nums, int bound) {
6 int count = 0, result = 0, current = 0;
7 for (int num : nums) {
8 if (num <= bound) {
9 current++;
10 } else {
11 current = 0;
12 }
13 result += current;
14 }
15 return result;
16}
17
18int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
19 return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
20}
21
22int main() {
23 vector<int> nums = {2, 1, 4, 3};
24 int left = 2, right = 3;
25 cout << numSubarrayBoundedMax(nums, left, right) << endl;
26 return 0;
27}Similar to the C implementation, this solution uses the function countSubarrays, which is applied twice to calculate ranges. The calculated difference gives the required result.
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.