# Number of Subarrays with Bounded Maximum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum)
Canonical: https://scaleengineer.com/dsa/problems/number-of-subarrays-with-bounded-maximum
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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
## 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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimized Brute Force
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]`.
**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.
**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).
### Explanation
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.

```java
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++) {
            int currentMax = -1;
            for (int j = i; j < n; j++) {
                currentMax = Math.max(currentMax, nums[j]);
                if (currentMax >= left && currentMax <= right) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### 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`.

## Single Pass with Sliding Window
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`.
**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.
**Pros:** Optimal time complexity.; Constant space complexity.
**Cons:** The logic can be a bit subtle to grasp initially, especially handling the three different cases.
### Explanation
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`.

```java
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int result = 0;
        int windowStart = 0;
        int countInWindow = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] >= left && nums[j] <= right) {
                countInWindow = j - windowStart + 1;
                result += countInWindow;
            } else if (nums[j] < left) {
                result += countInWindow;
            } else { // nums[j] > right
                windowStart = j + 1;
                countInWindow = 0;
            }
        }
        return result;
    }
}
```
### 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.

## Counting with Inclusion-Exclusion Principle
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        // Count of subarrays with max <= right
        int countRight = countLessEqual(nums, right);
        // Count of subarrays with max <= left - 1
        int countLeftMinus1 = countLessEqual(nums, left - 1);
        return countRight - countLeftMinus1;
    }

    // Helper function to count subarrays with max element <= bound
    private int countLessEqual(int[] nums, int bound) {
        int count = 0;
        int currentLength = 0;
        for (int num : nums) {
            if (num <= bound) {
                currentLength++;
            } else {
                currentLength = 0;
            }
            count += currentLength;
        }
        return count;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    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)

```