Number of Subarrays with Bounded Maximum

Problem Statement

You are provided with an integer array nums alongside two integers, left and right. Your task is to calculate the number of contiguous subarrays where the maximum element within each subarray falls between left and right inclusive. This problem ensures that the resulting count can be accommodated within a 32-bit integer.

Examples

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

Approach and Intuition

Evaluating Subarrays

To tackle this problem, we can leverage two pointers technique or a sliding window approach to efficiently determine valid subarrays that meet the criteria.

1. Two Pointers Technique: This involves maintaining a start and end pointer, initially both set to the start of the array.

2. Expand end Pointer: Increase the end pointer to explore new subarrays. For each position of end, you need to check if the current subarray (from start to end) contains a maximum value within the specified range [left, right].

3. Adjust start Pointer: If the maximum value in the current subarray exceeds right, move the start pointer rightwards until the max-value condition is satisfied again. This will help in excluding elements that push the subarray's maximum outside the desired range.

4. Count Valid Subarrays: For each position of end that forms a valid subarray with the current start, increment your count. The number of valid subarrays ending at end with different starting points (start) can be directly calculated if the maximum condition is satisfied.

5. Optimal Data Structures: A deque (double-ended queue) can be used to efficiently keep track of the maximum of the current subarray. This optimizes finding the maximum value to a constant time operation, which is crucial given the constraint on the size of nums.

Example Walkthrough

• Example 1:

  • For the input nums = [2,1,4,3] with left = 2 and right = 3, the subarrays [2], [2, 1], and [3] have their maximum values within [2, 3].
  • These subarrays are identified by expanding end and adjusting start to ensure the subarray's max falls within range.

• Example 2:

  • Here, nums = [2,9,2,5,6] with left = 2 and right = 8. The approach involves identifying each subarray where the maximum falls between 2 and 8. Due to the presence of 9 which is outside the range, only certain segments of the array contribute to the count like [2], [2,9,2] where segments get excluded when encountering 9.

By utilizing an efficient subarray tracking method and maintaining a constant-time check on the maximum value, the problem can be addressed efficiently within the provided constraints.

Solutions

class Solution {
    public int countSubarraysWithMaxWithinBounds(int[] nums, int low, int high) {
        return helper(nums, high) - helper(nums, low - 1);
    }
    
    public int helper(int[] nums, int limit) {
        int res = 0, count = 0;
        for (int num : nums) {
            count = num <= limit ? count + 1 : 0;
            res += count;
        }
        return res;
    }
}