What happens if you not resetting last_invalid when element > right?

Counts invalid subarrays leading to incorrect total Fix: Update last_invalid index whenever nums[i] > right

What happens if you counting subarrays with max < left as valid?

Overcounts subarrays that don't meet minimum max requirement Fix: Track last_valid index where element is within [left, right] and count accordingly

What happens if you off-by-one errors in counting valid subarrays ending at index?

Incorrect counts, often off by one or zero Fix: Use max(0, last_valid - last_invalid) to count valid subarrays ending at current index

Interview Prepknowing-what-to-trackmediumAmazonGoogleFacebook

Number of Subarrays with Bounded Maximum

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumHASH_MAPAmazonGoogleFacebook

Imagine you are analyzing user activity sessions, and you want to count how many continuous periods have a peak activity level within a certain range.

💡 This problem requires understanding how to efficiently count subarrays that satisfy a maximum constraint. Beginners often struggle because naive methods check all subarrays, which is too slow, and they don't know how to track boundaries or last invalid positions to optimize counting.

📋

Problem Statement

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the maximum element in that subarray is at least left and at most right.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^90 ≤ left ≤ right ≤ 10^9

💡

Example

Input"nums = [2,1,4,3], left = 2, right = 3"

Output3

The subarrays are [2], [2,1], and [3]. Each has max between 2 and 3.

Input"nums = [2,9,2,5,6], left = 2, right = 8"

Output7

Valid subarrays include [2], [2,9] is invalid because 9 > 8, so excluded. Counting all valid subarrays yields 7.

All elements less than left → output 0
All elements greater than right → output 0
Single element array within bounds → output 1
Array with all elements equal to left or right → output count of all subarrays

⚠️

Common Mistakes

Not resetting last_invalid when element > right

Counts invalid subarrays leading to incorrect total

✅ Update last_invalid index whenever nums[i] > right

Counting subarrays with max < left as valid

Overcounts subarrays that don't meet minimum max requirement

✅ Track last_valid index where element is within [left, right] and count accordingly

Using max function inside nested loops in brute force without caching

Leads to O(n^3) time, causing timeouts

✅ Update max incrementally in inner loop instead of recomputing

Off-by-one errors in counting valid subarrays ending at index

Incorrect counts, often off by one or zero

✅ Use max(0, last_valid - last_invalid) to count valid subarrays ending at current index

Confusing subarray max with subarray sum

Wrong approach and incorrect results

✅ Focus on max element tracking, not sum

🧠

Brute Force (Nested Loops Checking Each Subarray)

💡 This approach exists to build intuition by directly checking every possible subarray. It is simple but inefficient, helping beginners understand the problem's requirements before optimizing.

Intuition

Check every subarray, find its maximum, and count it if the max is within [left, right].

Algorithm

Initialize count to 0.
For each start index i in nums:
For each end index j from i to end:
Find max element in nums[i..j].
If max is between left and right, increment count.

💡 The nested loops and max calculation are straightforward but lead to repeated work and inefficiency.

</>

Code

def numSubarrayBoundedMax(nums, left, right):
    count = 0
    n = len(nums)
    for i in range(n):
        current_max = float('-inf')
        for j in range(i, n):
            current_max = max(current_max, nums[j])
            if left <= current_max <= right:
                count += 1
    return count

# Driver code
if __name__ == '__main__':
    print(numSubarrayBoundedMax([2,1,4,3], 2, 3))  # Output: 3

Line Notes

count = 0Initialize counter to accumulate valid subarrays

for i in range(n)Outer loop picks start index of subarray

current_max = float('-inf')Reset max for new subarray starting at i

for j in range(i, n)Inner loop extends subarray to end index j

current_max = max(current_max, nums[j])Update max element in current subarray

if left <= current_max <= rightCheck if current max is within bounds to count

public class Solution {
    public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currentMax = Integer.MIN_VALUE;
            for (int j = i; j < n; j++) {
                currentMax = Math.max(currentMax, nums[j]);
                if (currentMax >= left && currentMax <= right) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(numSubarrayBoundedMax(new int[]{2,1,4,3}, 2, 3)); // 3
    }
}

Line Notes

int count = 0;Initialize count of valid subarrays

for (int i = 0; i < n; i++)Outer loop selects start index

int currentMax = Integer.MIN_VALUE;Reset max for new subarray

for (int j = i; j < n; j++)Inner loop selects end index

currentMax = Math.max(currentMax, nums[j]);Update max in current subarray

if (currentMax >= left && currentMax <= right)Check if max is within bounds

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int currentMax = INT_MIN;
        for (int j = i; j < n; j++) {
            currentMax = max(currentMax, nums[j]);
            if (currentMax >= left && currentMax <= right) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {2,1,4,3};
    cout << numSubarrayBoundedMax(nums, 2, 3) << endl; // 3
    return 0;
}

Line Notes

int count = 0;Initialize count accumulator

for (int i = 0; i < n; i++)Outer loop for subarray start

int currentMax = INT_MIN;Reset max for each start index

for (int j = i; j < n; j++)Inner loop for subarray end

currentMax = max(currentMax, nums[j]);Update max element in subarray

if (currentMax >= left && currentMax <= right)Check if max is valid

function numSubarrayBoundedMax(nums, left, right) {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        let currentMax = -Infinity;
        for (let j = i; j < n; j++) {
            currentMax = Math.max(currentMax, nums[j]);
            if (currentMax >= left && currentMax <= right) {
                count++;
            }
        }
    }
    return count;
}

// Test
console.log(numSubarrayBoundedMax([2,1,4,3], 2, 3)); // 3

Line Notes

let count = 0;Initialize count of valid subarrays

for (let i = 0; i < n; i++)Outer loop picks subarray start

let currentMax = -Infinity;Reset max for each new start

for (let j = i; j < n; j++)Inner loop picks subarray end

currentMax = Math.max(currentMax, nums[j]);Update max in current subarray

if (currentMax >= left && currentMax <= right)Check if max is within bounds

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each up to n, and max updated in O(1) per iteration, total O(n^2).

💡 For n=20, this means about 400 operations, which is okay, but for n=10^5 it is 10^10 operations, too slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(1)`	No	N/A	Mention only - never code due to inefficiency
2. Track Last Invalid and Valid Indices	`O(n)`	`O(1)`	No	N/A	Code this approach for optimal solution
3. Inclusion-Exclusion Counting	`O(n)`	`O(1)`	No	N/A	Mention as alternative or if interviewer asks for different perspective

Practice

(1/5)

1. You are given an integer array and a number k. You need to count the number of contiguous subarrays that contain exactly k odd numbers. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use dynamic programming to store counts of subarrays ending at each index with exactly k odd numbers.

B. Use a brute force nested loop to check all subarrays and count odd numbers.

C. Use a sliding window with two pointers to count subarrays with at most k and k-1 odd numbers and subtract.

D. Use a greedy approach to expand and shrink the window whenever the odd count exceeds k.

3. Given the following Python code for summaryRanges, what is the final returned list when input is [1,2,3,5]?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        if start == end:
            ranges.append(str(nums[start]))
        else:
            ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

easy

A. ['1', '2', '3', '5']

B. ['1->3', '5']

C. ['1->2', '3->5']

D. ['1->3', '5->5']

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Trace prefix sums and first_occurrence updates.

Step 2: Update max_length when prefix sum repeats.

Final Answer:

Quick Check:

Solution

Step 1: Trace first range detection

Step 2: Append first range and move start

Final Answer:

Quick Check:

Solution

Step 1: Analyze loop iterations

Step 2: Confirm no nested loops or extra space

Final Answer:

Quick Check:

Solution

Step 1: Identify substring extraction logic

Step 2: Correct substring extraction

Final Answer:

Quick Check:

Ready to prove it?