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.
1public class Solution {
2 private static int countSubarrays(int[] nums, int bound) {
3 int count = 0, result = 0, current = 0;
4 for (int num : nums) {
5 if (num <= bound) {
6 current++;
7 } else {
8 current = 0;
9 }
10 result += current;
11 }
12 return result;
13 }
14
15 public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
16 return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
17 }
18
19 public static void main(String[] args) {
20 int[] nums = {2, 1, 4, 3};
21 int left = 2, right = 3;
22 System.out.println(numSubarrayBoundedMax(nums, left, right));
23 }
24}This Java implementation leverages the same logic in a method called countSubarrays which we invoke twice. By subtracting these results, we pinpoint the subarrays satisfying the condition.
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.