Log inSign up
mediumLeetCodeNot Started

Number of Subarrays with Bounded Maximum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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].

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
Explanation: The valid subarrays are [2], [2], [2, 5], [5], [2, 5, 6], [5, 6], [6]. Note that 9 is excluded because it is > 8.

Example 3:

Input: nums = [7,3,2,1], left = 8, right = 10
Output: 0
Explanation: No elements are in the range [8, 10], so 0 valid subarrays.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= left <= right <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Subarray counting principles
  • Two pointers and interval partitioning
  • Inclusion-Exclusion concept

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master 3-state classification: Barrier (> R), Valid Match ([L, R]), and Neutral Extender (< L).
  • Apply the Inclusion-Exclusion Principle: Count([L, R]) = Count(<= R) - Count(<= L - 1).
  • Implement the single-pass lastValid - lastInvalid pointer counting formula.
  • Handle 64-bit counts for large arrays (N = 105).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting subarrays whose maximum element satisfies a range condition [L, R].
  • Presence of barrier elements that completely invalidate any enclosing subarray (nums[i] > R).
  • Presence of neutral elements (nums[i] < L) that cannot start a valid subarray alone but can extend one.

Algorithmic Decision Tree:

  • If checking all subarrays -> O(N2) brute force (times out).
  • If counting with range bounds -> Count(max <= R) - Count(max <= L - 1) in O(N).
  • If single pass desired -> 3-State pointer tracking (lastValid - lastInvalid) in O(N) time and O(1) space.

Connected Patterns:

Subarray Product Less Than KCount Subarrays With Fixed BoundsMaximum Points You Can Obtain from Cards

1. Brute Force (Nested Loop Subarray Max)

Intuition

Fix start index i. Expand rightwards with index j, keeping a running maximum maxVal = max(maxVal, nums[j]). If maxVal > right, break (any larger subarray starting at i is also invalid). If left <= maxVal <= right, increment answer.

Algorithm

  1. Step 1: Initialize ans = 0.
  2. Step 2: For each i from 0 to n - 1:
  3. - Initialize maxVal = 0.
  4. - For each j from i to n - 1:
  5. - maxVal = max(maxVal, nums[j]).
  6. - If maxVal > right, break.
  7. - If maxVal >= left, ans++.
  8. Step 3: Return ans.

Brute Force (Nested Loop Subarray Max) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 1, 2, 4, 3]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
2
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=2. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int numSubarrayBoundedMax(std::vector<int>& nums, int left, int right) {
8 int n = nums.size();
9 int ans = 0;
10
11 for (int i = 0; i < n; i++) {
12 int maxVal = 0;
13 for (int j = i; j < n; j++) {
14 maxVal = std::max(maxVal, nums[j]);
15 if (maxVal > right) break;
16 if (maxVal >= left) ans++;
17 }
18 }
19 return ans;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::vector<int> nums = {2, 1, 4, 3};
26 std::cout << "Subarrays: " << sol.numSubarrayBoundedMax(nums, 2, 3) << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Nested Loop Subarray Max).
  • Space complexity: O(1) — Space complexity for Brute Force (Nested Loop Subarray Max).

Why Brute Force Doesn't Scale:

For N = 100,000, N2 = 1010 operations, causing TLE. The single-pass 3-state tracking counts valid starting points in O(1) per element, completing in ~100,000 operations (< 3 ms).

For N = 100,000: Brute force takes ~10 billion operations; Single-pass tracking takes ~100,000 operations (~100,000x speedup).

2. Better (Inclusion-Exclusion via Count Function)

Intuition

Define helper countSubarrays(bound): counts subarrays containing only elements <= bound. Any segment of length len with elements <= bound has len * (len + 1) / 2 contiguous subarrays. The answer is countSubarrays(right) - countSubarrays(left - 1).

Algorithm

  1. Step 1: In helper count(bound):
  2. - Initialize total = 0, currLen = 0.
  3. - For each x in nums: if x <= bound, currLen++, total += currLen; else currLen = 0.
  4. - Return total.
  5. Step 2: Return count(right) - count(left - 1).

Better (Inclusion-Exclusion via Count Function) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 1, 2, 4, 3]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
2
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=2. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5private:
6 int count(const std::vector<int>& nums, int bound) {
7 int total = 0, currLen = 0;
8 for (int x : nums) {
9 if (x <= bound) {
10 currLen++;
11 total += currLen;
12 } else {
13 currLen = 0;
14 }
15 }
16 return total;
17 }
18
19public:
20 int numSubarrayBoundedMax(std::vector<int>& nums, int left, int right) {
21 return count(nums, right) - count(nums, left - 1);
22 }
23};
24
25int main() {
26 Solution sol;
27 std::vector<int> nums = {2, 1, 4, 3};
28 std::cout << "Better Subarrays: " << sol.numSubarrayBoundedMax(nums, 2, 3) << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Inclusion-Exclusion via Count Function).
  • Space complexity: O(N) — Space complexity for Better (Inclusion-Exclusion via Count Function).

3. Optimal (One-Pass 3-State Pointer Tracking)

Intuition

For each index i: 1. If nums[i] > right: this element invalidates any enclosing subarray. Update lastInvalid = i, and reset lastValid = -1. 2. If left <= nums[i] <= right: this element is a valid maximum. Update lastValid = i. 3. If nums[i] < left: this element is smaller than left. It cannot start a valid subarray on its own, but it CAN extend any valid subarray that already includes the most recent lastValid element! At every step, the number of valid subarrays ending at index i is max(0, lastValid - lastInvalid).

Algorithm

  1. Step 1: Initialize ans = 0, lastInvalid = -1, and lastValid = -1.
  2. Step 2: For each i from 0 to nums.length - 1:
  3. - If nums[i] > right: lastInvalid = i, lastValid = -1.
  4. - Else if nums[i] >= left: lastValid = i.
  5. - If lastValid > lastInvalid: ans += (lastValid - lastInvalid).
  6. Step 3: Return ans.

Optimal (One-Pass 3-State Pointer Tracking) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 1, 2, 4, 3]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
2
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=2. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int numSubarrayBoundedMax(std::vector<int>& nums, int left, int right) {
8 int ans = 0;
9 int lastInvalid = -1;
10 int lastValid = -1;
11
12 for (int i = 0; i < (int)nums.size(); i++) {
13 if (nums[i] > right) {
14 lastInvalid = i;
15 lastValid = -1;
16 } else if (nums[i] >= left) {
17 lastValid = i;
18 }
19
20 if (lastValid > lastInvalid) {
21 ans += (lastValid - lastInvalid);
22 }
23 }
24 return ans;
25 }
26};
27
28int main() {
29 Solution sol;
30 std::vector<int> nums = {2, 1, 4, 3};
31 std::cout << "Optimal Subarrays: " << sol.numSubarrayBoundedMax(nums, 2, 3) << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (One-Pass 3-State Pointer Tracking).
  • Space complexity: O(1) — Space complexity for Optimal (One-Pass 3-State Pointer Tracking).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Loop Maximum Tracking)O(N^2)O(1)For each starting index i, expand j while maintaining running maximum. Increment count if max in [left, right].Iterating through all O(N2) subarrays.
2.Better (Inclusion-Exclusion via Count Function)O(N)O(1)Count subarrays with max <= right, then subtract subarrays with max <= left - 1.Two sequential array traversals.
3.Optimal (One-Pass 3-State Pointer Tracking)OptimalO(N)O(1)Single pass maintaining lastValid and lastInvalid. Adds max(0, lastValid - lastInvalid) at every index.Single pass scan bound.

Common Pitfalls & Crucial Edge Cases

Treating elements < left as invalidating barriers

Elements < left do NOT invalidate a subarray; they can extend an existing subarray as long as a valid element in [left, right] was previously encountered.

Forgetting to reset `lastValid` when `nums[i] > right`

If lastValid is not cleared when a barrier > right appears, subsequent elements < left will falsely pair with stale elements behind the barrier.

Integer overflow on large answers

With N = 105, answer can reach ≈ 5 × 109. In competitive programming templates, ensure 64-bit accumulator.

Crucial Edge Cases to Validate:

  • All elements > right (nums = [5, 6, 7], left = 1, right = 3): Every element resets pointers, returns 0.
  • All elements < left (nums = [1, 1, 1], left = 2, right = 5): lastValid remains -1 throughout, returns 0.
  • All elements within [left, right] (nums = [2, 2, 2], left = 1, right = 3): Returns N(N+1)/2 = 6.
  • Single element matching / mismatching (nums = [3], left = 2, right = 4 -> 1; nums = [1] -> 0).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the 3-state classification: Barrier (> R), Valid Match ([L, R]), and Extender (< L).
  2. Demonstrate the Inclusion-Exclusion formula Count(<= R) - Count(<= L - 1) as a clean alternative if the interviewer asks for a modular design.
  3. Highlight that lastValid - lastInvalid gives the exact count of valid start indices in O(1).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the role of an element nums[i] < left in this problem?

2.Why does count(max <= right) - count(max <= left - 1) yield the exact number of valid subarrays?

3.What is the time complexity of the optimal single-pass pointer tracking approach?

Back to DSA Sheet