{x}
blog image

Number of Subarrays with Bounded Maximum

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

 

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

Solution Explanation for Number of Subarrays with Bounded Maximum

This problem asks to find the number of contiguous subarrays within a given array nums where the maximum element in each subarray falls within the range [left, right]. Two solutions are presented below, differing significantly in their approach and time complexity.

Solution 1: Inclusion-Exclusion Principle

This solution cleverly utilizes the inclusion-exclusion principle. It defines a helper function f(x) that counts the number of subarrays whose maximum value is less than or equal to x. The final answer is then calculated as f(right) - f(left - 1).

How it works:

  1. f(x) Function: This function iterates through the nums array. It maintains a counter t, which represents the length of the current subarray whose maximum value is less than or equal to x. If an element v exceeds x, the counter t is reset to 0. Otherwise, t is incremented. The total count cnt is updated by adding t in each iteration, effectively counting all subarrays ending at the current position with a maximum value less than or equal to x.

  2. Inclusion-Exclusion: f(right) counts subarrays with a maximum ≤ right. f(left - 1) counts subarrays with a maximum ≤ left - 1. Subtracting the second from the first leaves only the subarrays whose maximum is within the range [left, right].

Time Complexity: O(N), where N is the length of nums. The array is traversed twice (once for f(right) and once for f(left-1)). Space Complexity: O(1), constant extra space is used.

Solution 2: Monotonic Stack and Range Calculation

This approach is more complex but potentially more efficient in some scenarios (though still linear on average). It uses a monotonic stack to find the left and right boundaries for each element's maximum range.

How it works:

  1. Left Boundary (l array): A monotonic decreasing stack is used to find the nearest element to the left that is smaller. This determines how far to the left a subarray can extend while still having the current element as its maximum. l[i] stores this index. If no such element exists, l[i] is -1.

  2. Right Boundary (r array): A similar monotonic increasing stack is used to find the nearest element to the right that is less than or equal to the current element. This determines how far to the right a subarray can extend. r[i] stores this index. If no such element exists, r[i] is n (length of the array).

  3. Range Calculation: For each element nums[i], if it's within the range [left, right], the number of subarrays with that element as the maximum is calculated as (i - l[i]) * (r[i] - i). This formula calculates the number of subarrays extending to the left and right of the index i. The total count is the sum of these contributions for all valid elements.

Time Complexity: O(N) on average, due to stack operations (it might degrade to O(N^2) in worst-case scenarios if the input is structured in a way that leads to many stack operations, though this is rare). Space Complexity: O(N) to store the l and r arrays and the stack.

In summary:

Solution 1 is simpler and generally preferred for its clarity and guaranteed linear time complexity. Solution 2 offers an alternative approach, utilizing advanced data structures, but its time complexity is less predictable. Choose the solution that best suits your needs and understanding. For most cases, Solution 1 is the more practical and efficient choice.