Number of Subarrays with Bounded Maximum

Med

#0749Time: O(N^3), where N is the number of elements in `nums`. The two outer loops run in O(N^2) to generate all subarrays, and for each subarray, we spend up to O(N) time to find its maximum.Space: O(1), as we only use a constant number of variables to store state (indices, max value, and count).1 company

Patterns

Two Pointers

Data structures

Array

Companies

Quora

Prompt

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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= left <= right <= 10⁹

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate every possible contiguous subarray, find the maximum element for each one, and then check if this maximum falls within the given bounds [left, right]. This method is easy to conceptualize but computationally expensive.

Algorithm

Initialize a counter count to 0.
Use a nested loop with index i from 0 to n-1 to select the starting element of the subarray.
Use another nested loop with index j from i to n-1 to select the ending element of the subarray.
For each subarray nums[i...j], use a third loop with index k from i to j to find the maximum element maxVal.
Check if maxVal is within the range [left, right]. If it is, increment count.
After all loops complete, return count.

Walkthrough

This approach systematically checks every single subarray. It uses a pair of nested loops to define the start and end points of a subarray. For each subarray defined, a third loop is used to iterate through its elements to find the maximum value. This maximum is then compared against the left and right bounds. If it satisfies the condition left <= max <= right, a counter is incremented. While correct, the cubic time complexity makes it impractical for the given constraints.

1class Solution {2    public int numSubarrayBoundedMax(int[] nums, int left, int right) {3        int count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            for (int j = i; j < n; j++) {7                int maxVal = -1;8                // Find max in the subarray nums[i...j]9                for (int k = i; k <= j; k++) {10                    maxVal = Math.max(maxVal, nums[k]);11                }12                if (maxVal >= left && maxVal <= right) {13                    count++;14                }15            }16        }17        return count;18    }19}

Complexity

Time

O(N^3), where N is the number of elements in `nums`. The two outer loops run in O(N^2) to generate all subarrays, and for each subarray, we spend up to O(N) time to find its maximum.

Space

O(1), as we only use a constant number of variables to store state (indices, max value, and count).

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to be correct.

Cons

Extremely inefficient due to three nested loops.
Will result in a 'Time Limit Exceeded' error for even moderately sized inputs.

We can improve upon the brute-force approach by optimizing how we find the maximum of each subarray. Instead of recalculating the maximum from scratch for every subarray, we can maintain the maximum of the current subarray nums[i...j] and update it in O(1) time when we extend it to nums[i...j+1].

Algorithm

Initialize a counter count to 0.
Use a loop with index i from 0 to n-1 to fix the starting element of subarrays.
Inside this loop, initialize currentMax = -1.
Use a nested loop with index j from i to n-1 to extend the subarray.
In the inner loop, update currentMax = Math.max(currentMax, nums[j]).
Check if the currentMax is within the range [left, right]. If it is, increment count.
After the loops complete, return count.

Walkthrough

This method reduces the complexity from cubic to quadratic. We iterate through all possible start points i of a subarray. For each start point, we iterate through all possible end points j. As we extend the subarray by one element nums[j], we update the maximum value seen so far in O(1) time. This currentMax for the subarray nums[i...j] is then checked against the bounds. This avoids the third, innermost loop of the previous approach.

1class Solution {2    public int numSubarrayBoundedMax(int[] nums, int left, int right) {3        int count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            int currentMax = -1;7            for (int j = i; j < n; j++) {8                currentMax = Math.max(currentMax, nums[j]);9                if (currentMax >= left && currentMax <= right) {10                    count++;11                }12            }13        }14        return count;15    }16}

Complexity

Time

O(N^2), where N is the length of `nums`. We have two nested loops to consider all N*(N+1)/2 subarrays, with O(1) work inside the inner loop.

Space

O(1), as we only use a few extra variables.

Trade-offs

Pros

A significant improvement over the O(N^3) approach.
Still relatively easy to implement.

Cons

Still inefficient for large inputs as its time complexity is quadratic.
Will time out on the given constraints (N up to 10^5).

A linear time solution can be achieved by making a single pass through the array. We can count the number of valid subarrays ending at each index j. The total count is the sum of these counts for all j. We use a sliding window approach, where the window contains elements that are all less than or equal to right.

Algorithm

Initialize result = 0, windowStart = 0, and countInWindow = 0.
Iterate through the array with an index j from 0 to n-1.
Case 1: nums[j] is in the range [left, right]
- The element nums[j] can start new valid subarrays. All subarrays ending at j within the current window [windowStart, j] are valid. The number of such subarrays is j - windowStart + 1.
- Update countInWindow = j - windowStart + 1.
- Add countInWindow to result.
Case 2: nums[j] < left
- The element nums[j] itself doesn't satisfy the lower bound, but it can extend existing valid subarrays. The number of valid subarrays ending at j is the same as the number of valid subarrays ending at j-1.
- Add the last calculated countInWindow to result.
Case 3: nums[j] > right
- This element breaks the condition for any subarray that includes it. It acts as a separator.
- Reset the window by setting windowStart = j + 1.
- Reset countInWindow = 0.
Return result after the loop.

Walkthrough

We iterate through the array and maintain a count of valid subarrays ending at the current position. Let's use j as our main pointer. We'll also need windowStart to mark the beginning of a sequence of numbers all <= right, and countInWindow to store the number of valid subarrays ending at the last element that was in the [left, right] range.

When nums[j] is in [left, right], it validates all subarrays ending at j within the current window (from windowStart to j). The number of such subarrays is j - windowStart + 1. We update countInWindow and add it to our total result.

When nums[j] < left, it cannot start a new valid subarray on its own, but it can extend the countInWindow valid subarrays from the previous step. So, we add countInWindow to result.

When nums[j] > right, it invalidates any subarray containing it. We reset our window and counts, moving windowStart to j + 1.

1class Solution {2    public int numSubarrayBoundedMax(int[] nums, int left, int right) {3        int result = 0;4        int windowStart = 0;5        int countInWindow = 0;6        for (int j = 0; j < nums.length; j++) {7            if (nums[j] >= left && nums[j] <= right) {8                countInWindow = j - windowStart + 1;9                result += countInWindow;10            } else if (nums[j] < left) {11                result += countInWindow;12            } else { // nums[j] > right13                windowStart = j + 1;14                countInWindow = 0;15            }16        }17        return result;18    }19}

Complexity

Time

O(N), as we iterate through the input array only once.

Space

O(1), as we only use a few variables to keep track of our state.

Trade-offs

Pros

Optimal time complexity.
Constant space complexity.

Cons

The logic can be a bit subtle to grasp initially, especially handling the three different cases.

This elegant approach transforms the problem into a simpler one. The number of subarrays with a maximum in the range [left, right] is equivalent to the number of subarrays with a maximum less than or equal to right, minus the number of subarrays with a maximum less than left. This reduces the problem to solving a simpler subproblem: counting subarrays with a maximum up to a certain bound.

Algorithm

The main idea is to use the inclusion-exclusion principle: count(max in [L, R]) = count(max <= R) - count(max <= L-1).
Create a helper function countLessEqual(bound) that counts the number of subarrays whose maximum element is less than or equal to bound.
Inside countLessEqual(bound):
- Initialize count = 0 and currentLength = 0.
- Iterate through each num in the input array.
- If num <= bound, it means the current contiguous block of valid numbers is extended. Increment currentLength.
- If num > bound, the block is broken. Reset currentLength = 0.
- In each step, add currentLength to count. This is because an element extending a block of length k-1 to k creates k new valid subarrays ending at the current position.
- Return the total count.
In the main function, calculate countLessEqual(nums, right) - countLessEqual(nums, left - 1) and return the result.

Walkthrough

Let count(x) be the number of subarrays where the maximum element is at most x. A subarray has a maximum of at most x if and only if all of its elements are at most x. The problem asks for the number of subarrays where the maximum m satisfies left <= m <= right. This is exactly count(right) - count(left - 1).

So, we can write a helper function countLessEqual(bound) that solves this simpler problem. This function can be implemented in a single pass. We iterate through the array, keeping track of the length of the current contiguous segment of numbers that are all less than or equal to bound. If we have a segment of length k, it contains k subarrays ending at the last element. By summing these lengths as we iterate, we get the total count.

1class Solution {2    public int numSubarrayBoundedMax(int[] nums, int left, int right) {3        // Count of subarrays with max <= right4        int countRight = countLessEqual(nums, right);5        // Count of subarrays with max <= left - 16        int countLeftMinus1 = countLessEqual(nums, left - 1);7        return countRight - countLeftMinus1;8    }9 10    // Helper function to count subarrays with max element <= bound11    private int countLessEqual(int[] nums, int bound) {12        int count = 0;13        int currentLength = 0;14        for (int num : nums) {15            if (num <= bound) {16                currentLength++;17            } else {18                currentLength = 0;19            }20            count += currentLength;21        }22        return count;23    }24}

Complexity

Time

O(N), because we perform two separate passes over the array, each taking O(N) time. This simplifies to O(N).

Space

O(1), as we only use a few variables for counting within each pass.

Trade-offs

Pros

Optimal O(N) time complexity.
Very clean and modular code.
The underlying principle is a powerful technique applicable to other range-based counting problems.

Cons

Requires the insight to reframe the problem, which might not be immediately obvious.

Solutions

Solution

1class Solution {2public3  int numSubarrayBoundedMax(int[] nums, int left, int right) {4    return f(nums, right) - f(nums, left - 1);5  }6private7  int f(int[] nums, int x) {8    int cnt = 0, t = 0;9    for (int v : nums) {10      t = v > x ? 0 : t + 1;11      cnt += t;12    }13    return cnt;14  }15}

1class Solution {2public:3  int numSubarrayBoundedMax(vector<int> &nums, int left, int right) {4    auto f = [&](int x) {5      int cnt = 0, t = 0;6      for (int &v : nums) {7        t = v > x ? 0 : t + 1;8        cnt += t;9      }10      return cnt;11    };12    return f(right) - f(left - 1);13  }14};

1class Solution:2    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int: def f(x): cnt = t = 0 for v in nums: t = 0 if v > x else t + 1 cnt += t return cnt return f(right) - f(left - 1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int numSubarrayBoundedMax(int[] nums, int left, int right) {4    return f(nums, right) - f(nums, left - 1);5  }6private7  int f(int[] nums, int x) {8    int cnt = 0, t = 0;9    for (int v : nums) {10      t = v > x ? 0 : t + 1;11      cnt += t;12    }13    return cnt;14  }15}

1class Solution {2public:3  int numSubarrayBoundedMax(vector<int> &nums, int left, int right) {4    auto f = [&](int x) {5      int cnt = 0, t = 0;6      for (int &v : nums) {7        t = v > x ? 0 : t + 1;8        cnt += t;9      }10      return cnt;11    };12    return f(right) - f(left - 1);13  }14};

1class Solution:2    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int: def f(x): cnt = t = 0 for v in nums: t = 0 if v > x else t + 1 cnt += t return cnt return f(right) - f(left - 1)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.