Number of Subarrays with Bounded Maximum

Updated on 26 June, 2025
Number of Subarrays with Bounded Maximum header image

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

  • Java
java
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;
    }
}

The provided Java solution focuses on finding the count of subarrays within an array where the maximum value lies between two defined bounds, low and high.

  • Utilize two function calls where each call efficiently calculates the cumulative count of all subarrays with maximum values less than or equal to a given limit.
  • The main function, countSubarraysWithMaxWithinBounds, leverages the helper function helper to achieve this by taking the difference between:
    • The count of subarrays with maximum values less than or equal to high.
    • The count of subarrays with maximum values less than low - 1 (essentially the subarrays which don't meet the lower bound constraint).

The helper function operates by iterating through each element of the array nums and maintaining a running count (count) of valid subarrays ending at each position that meet the condition specified by the 'limit' parameter. The result (res) aggregates these valid counts across the entire array, being incremented continually by the value of count at each step which resets whenever a number exceeds the limit. This efficient approach allows each element to be processed once, providing an overall time complexity of O(n), where n represents the number of elements in nums.

Comments

No comments yet.