Number of Subarrays with Bounded Maximum

MEDIUM

Description

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

Checkout 4 different approaches to solve Number of Subarrays with Bounded Maximum. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant number of variables to store state (indices, max value, and count).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Subarrays with Bounded Maximum. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Subarrays with Bounded Maximum

Patterns:

Two Pointers

Data Structures:

Array

Companies:

Quora |