Scale Engineer

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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= left <= right <= 109

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.

class Solution {    public int numSubarrayBoundedMax(int[] nums, int left, int right) {        int count = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                int maxVal = -1;                // Find max in the subarray nums[i...j]                for (int k = i; k <= j; k++) {                    maxVal = Math.max(maxVal, nums[k]);                }                if (maxVal >= left && maxVal <= right) {                    count++;                }            }        }        return count;    }}

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.

Solutions

class Solution {public  int numSubarrayBoundedMax(int[] nums, int left, int right) {    return f(nums, right) - f(nums, left - 1);  }private  int f(int[] nums, int x) {    int cnt = 0, t = 0;    for (int v : nums) {      t = v > x ? 0 : t + 1;      cnt += t;    }    return cnt;  }}

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 →

Next problem