Number of Subarrays with Bounded Maximum

📋

Problem

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.

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

Edge cases: All elements less than left → output 0All elements greater than right → output 0Single element array within bounds → output 1

</>

IDE

def numSubarrayBoundedMax(nums: list[int], left: int, right: int) -> int:public int numSubarrayBoundedMax(int[] nums, int left, int right)int numSubarrayBoundedMax(vector<int>& nums, int left, int right)function numSubarrayBoundedMax(nums, left, right)

def numSubarrayBoundedMax(nums, left, right):
    # Write your solution here
    pass

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    // Write your solution here
    return 0;
}

function numSubarrayBoundedMax(nums, left, right) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Fails to count any subarrays when elements are within bounds; likely missing counting logic.✅ Implement counting of valid subarrays ending at each index by tracking last invalid index and incrementing count accordingly.

Wrong: 6Overcounts subarrays by not resetting last invalid index when element > right, counting invalid subarrays.✅ Reset last invalid index to current index when nums[i] > right to exclude invalid subarrays.

Wrong: 3Undercounts subarrays by excluding those with max equal to left or right bounds.✅ Include subarrays where max is exactly equal to left or right in counting logic.

Wrong: TLEUses brute force O(n^2) approach causing timeout on large inputs.✅ Optimize to O(n) by tracking last invalid index and counting valid subarrays ending at each index.

✓

Test Cases

Make sure your solution handles empty and single-element arrays correctly before moving on.

Focus on tricky cases where greedy approaches fail; track last invalid index precisely.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[2,1,4,3],"left":2,"right":3}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Consider how to count subarrays with max in the given range.

💡 Track the last index where an element was out of bounds and count valid subarrays ending at each index.

💡 Use variables to track last invalid position and count valid subarrays incrementally.

Why it failed: Incorrect count due to not tracking last invalid index properly; fix by updating last invalid index when element > right.

✓ Correctly counts subarrays with max in [left, right] using last invalid tracking.

t1_02basic

Input{"nums":[1,2,3,4],"left":2,"right":3}

Expected3

⏱ Performance - must finish in 2000ms

Valid subarrays are [2], [2,3], and [3]. The element 4 is greater than right, so subarrays including 4 are invalid.

💡 Check how elements greater than right affect counting.

💡 Remember to reset last invalid index when element > right.

💡 Count valid subarrays ending at each index by subtracting last invalid index from current index.

Why it failed: Fails to reset last invalid index on elements > right, causing overcount; fix by resetting last invalid index properly.

✓ Properly handles elements > right and counts valid subarrays.

t2_01edge

Input{"nums":[],"left":1,"right":2}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so count is 0.

💡 Consider what happens when input array is empty.

💡 No subarrays exist if array length is zero.

💡 Return 0 immediately if nums is empty.

Why it failed: Code does not handle empty array, causing errors or wrong count; fix by returning 0 when nums is empty.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[1],"left":1,"right":1}

Expected1

⏱ Performance - must finish in 2000ms

Single element equal to left and right bounds counts as one valid subarray.

💡 Check single element arrays carefully.

💡 If element is within [left, right], count is 1.

💡 Return 1 if single element in bounds, else 0.

Why it failed: Fails single element case by not checking bounds correctly; fix by including single element check.

✓ Correctly counts single element subarray within bounds.

t2_03edge

Input{"nums":[0,0,0],"left":1,"right":2}

Expected0

⏱ Performance - must finish in 2000ms

All elements less than left, so no valid subarrays.

💡 Consider arrays where all elements are less than left bound.

💡 No subarray can have max in [left, right] if all elements < left.

💡 Return 0 if no elements meet lower bound.

Why it failed: Incorrectly counts subarrays when all elements < left; fix by ensuring max >= left in counting logic.

✓ Correctly returns 0 when all elements < left.

t3_01corner

Input{"nums":[2,2,2],"left":2,"right":2}

Expected6

⏱ Performance - must finish in 2000ms

All subarrays have max = 2, which is within bounds; total subarrays = n*(n+1)/2 = 6.

💡 Check arrays where all elements equal left or right.

💡 All subarrays are valid if max equals bounds.

💡 Count total subarrays n*(n+1)/2 when all elements in bounds.

Why it failed: Fails to count all subarrays when all elements equal bounds; fix by not excluding subarrays with max == left or right.

✓ Correctly counts all subarrays when all elements equal bounds.

t3_02corner

Input{"nums":[1,4,2,3],"left":2,"right":3}

Expected3

⏱ Performance - must finish in 2000ms

Valid subarrays: [2], [3], [2,3]. Element 4 > right resets last invalid index.

💡 Beware of greedy approaches that count subarrays incorrectly.

💡 Track last invalid index carefully when elements > right appear.

💡 Count valid subarrays ending at each index by subtracting last invalid index.

Why it failed: Greedy approach overcounts by ignoring last invalid index reset; fix by updating last invalid index on elements > right.

✓ Correctly handles last invalid index and counts valid subarrays.

t3_03corner

Input{"nums":[2,1,2,1,2],"left":2,"right":2}

Expected9

⏱ Performance - must finish in 2000ms

Only elements equal to 2 count as max; subarrays with max=2 are counted correctly.

💡 Distinguish between max < left and max in [left, right].

💡 Count subarrays with max exactly equal to bounds correctly.

💡 Use last invalid index and count valid subarrays ending at each index.

Why it failed: Confuses max < left with max in bounds, undercounting; fix by including subarrays with max == left or right.

✓ Correctly counts subarrays with max equal to bounds.

t4_01performance

Input{"nums":[1000000000,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"left":1,"right":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) solution must complete within 2 seconds; brute force O(n^2) will time out.

💡 Focus on O(n) time complexity solutions.

💡 Avoid nested loops; track last invalid index and count valid subarrays.

💡 Use prefix sums or incremental counting to achieve linear time.

Why it failed: Brute force or O(n^2) approach causes TLE; fix by implementing O(n) tracking last invalid index method.

✓ Solution runs in O(n) time confirming efficient complexity.

Practice

1. You are given a sorted list of unique integers and need to summarize consecutive sequences as ranges (e.g., [0,1,2,4,5,7] -> ['0->2','4->5','7']). Which approach guarantees an optimal O(n) time solution with minimal extra space?

easy

A. Using two pointers to scan the list once, expanding the end pointer while consecutive numbers continue, then recording ranges.

B. Using nested loops to check every possible range start and end, appending ranges when sequences break.

C. Using dynamic programming to store the longest consecutive subsequence ending at each index and reconstruct ranges.

D. Using a greedy approach that picks the next number if it is consecutive, otherwise starts a new range, but restarts scanning from the beginning each time.

Solution

1. Step 1: Understand the problem constraints

   The input is sorted and unique, so consecutive sequences can be detected by checking if nums[end + 1] == nums[end] + 1.

2. Step 2: Identify the optimal approach

   Two pointers allow a single pass: one pointer marks the start of a range, the other expands until the sequence breaks, then record the range and move start pointer forward.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers scan once -> O(n) time and O(n) space for output [OK]

Hint: Two pointers scan sorted list once for consecutive ranges [OK]

Common Mistakes:

• Thinking nested loops are necessary
• Confusing DP with this linear scan
• Restarting scan repeatedly wastes time

2. What is the time complexity of the optimal prefix sum with hash map solution for finding the longest contiguous subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n) because each element is processed once with constant-time hash map operations

B. O(n) but with O(n²) space for storing all prefix sums

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n²) due to nested loops scanning subarrays

Solution

1. Step 1: Identify the single loop over the array

   The algorithm iterates once over n elements, updating prefix_sum and hash map.

2. Step 2: Confirm hash map operations are O(1) average

   Insertion and lookup in hash map are average O(1), so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is O(n²), no sorting involved, space is O(n) not O(n²) [OK]

Hint: Hash map lookups are average O(1), single pass over array [OK]

Common Mistakes:

• Confusing brute force O(n²) with optimal
• Assuming hash map is O(log n)
• Overestimating space complexity

3. What is the time complexity of the optimal two-pointer approach for the Summary Ranges problem on an input list of length n?

medium

A. O(n log n) due to sorting the input before scanning for ranges.

B. O(n²) because the inner while loop can run up to n times for each start pointer.

C. O(n) because each element is visited at most twice by the two pointers combined.

D. O(n) but with O(n) auxiliary space for storing the output ranges.

Solution

1. Step 1: Analyze outer and inner loops

   The outer loop advances start pointer, inner loop advances end pointer; together they move forward without revisiting elements.

2. Step 2: Confirm total iterations

   Each element is visited at most twice (once by start, once by end), so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two pointers linear scan -> O(n) time [OK]

Hint: Two pointers each move forward once -> O(n) time [OK]

Common Mistakes:

• Assuming inner loop restarts fully causing O(n²)
• Confusing sorting cost if input is already sorted
• Ignoring that output space is separate from time complexity

4. Suppose the problem changes: now you want to count the number of subarrays with exactly k odd numbers, but the array can contain negative integers and zeros. Which modification to the sliding window approach is necessary to handle this correctly?

hard

A. Add extra conditions to handle zeros separately in the sliding window.

B. No change needed; the existing sliding window code works for any integers.

C. Use a prefix sum hashmap approach instead, since sliding window fails with negative numbers.

D. Modify the odd number check to use absolute value: check if abs(nums[i]) % 2 == 1.

Solution

1. Step 1: Identify how odd numbers are detected

   The code checks if nums[i] % 2 == 1, which fails for negative odd numbers (e.g., -1 % 2 == -1 in Python).

2. Step 2: Fix odd number detection

   Using abs(nums[i]) % 2 == 1 correctly identifies odd numbers regardless of sign.

3. Step 3: Confirm sliding window logic remains valid

   Once odd detection is fixed, the sliding window approach works as before.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   abs() fixes odd detection for negatives [OK]

Hint: Use abs() to detect odd numbers with negatives [OK]

Common Mistakes:

• Assuming % 2 == 1 works for negatives
• Switching to prefix sums unnecessarily
• Overcomplicating zero handling

5. Suppose the problem is modified so that characters in t can be reused unlimited times in the substring (i.e., the substring must contain at least one occurrence of each character in t, but counts do not matter). Which of the following algorithmic changes correctly adapts the sliding window approach?

hard

A. Keep frequency counts but ignore counts when checking if window is valid; only check presence of characters

B. No changes needed; the original frequency counting approach works as is

C. Use the original frequency map and formed count but reset formed to zero after each window

D. Use a set to track presence of required characters and expand/shrink window until all are present

Solution

1. Step 1: Understand problem change

   Now only presence of each character in t is required, not counts. So frequency counts are unnecessary; presence tracking suffices.

2. Step 2: Adapt algorithm

   Using a set to track which required characters are currently in the window allows efficient checking. Expand window until all required chars are present, then shrink to minimize.

3. Step 3: Why other options fail

   Ignoring counts but keeping frequency maps wastes time and complicates logic. Resetting formed to zero after each window breaks continuity. Original approach requires exact counts, so no changes is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Presence tracking with sets fits the relaxed requirement [OK]

Hint: Presence tracking replaces frequency counting [OK]

Common Mistakes:

• Ignoring that counts no longer matter
• Trying to reuse frequency counts unnecessarily