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

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting subarrays with exactly k odd numbers efficiently.

2. Step 2: Evaluate approaches

   Brute force is O(n^2), DP is complex and not straightforward here, greedy alone doesn't guarantee correctness. Sliding window with two pointers counting at most k and k-1 odd numbers and subtracting is optimal and linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window approach runs in O(n) time [OK]

Hint: Sliding window with at most k counts is optimal [OK]

Common Mistakes:

• Thinking greedy alone solves it optimally
• Assuming DP is needed
• Using brute force for large inputs

2. Given the following code and input nums = [3,1,1,1,5], x = 5, what is the returned value?

easy

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate totalSum and target

   totalSum = 3+1+1+1+5 = 11; target = 11 - 5 = 6.

2. Step 2: Use sliding window to find longest subarray summing to 6

   Window expands: [3] sum=3, [3,1] sum=4, [3,1,1] sum=5, [3,1,1,1] sum=6 -> max_len=4; next, add 5 sum=11 > 6, shrink from left: remove 3 sum=8 >6, remove 1 sum=7 >6, remove 1 sum=6 -> max_len=4 remains (subarray [1,1,1]).

3. Step 3: Calculate minimum operations

   Minimum removals = array length - max_len = 5 - 4 = 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Longest subarray length 4 -> min ops = 1 [OK]

Hint: Sliding window finds longest subarray sum [OK]

Common Mistakes:

• Off-by-one errors in window length calculation
• Miscomputing sums when shrinking window
• Confusing min operations with longest subarray length

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

Solution

1. Step 1: Trace first range detection

   start=0 (nums[0]=1), end moves from 0 to 2 because nums[1]=2 and nums[2]=3 are consecutive.

2. Step 2: Append first range and move start

   Append '1->3', then start=3 (nums[3]=5), end=3, no consecutive next element, append '5'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Ranges correctly summarize consecutive sequences [OK]

Hint: Two pointers expand end while consecutive -> correct ranges [OK]

Common Mistakes:

• Appending single elements as ranges like '5->5'
• Splitting consecutive sequences incorrectly
• Off-by-one errors in inner loop

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

5. What is the time complexity of the optimal sliding window algorithm that uses two frequency arrays and a match count to find all anagrams of p in s?

medium

A. O(n * m), where n = length of s and m = length of p

B. O(n * 26), where n = length of s

C. O(n), where n = length of s

D. O(n + m), where n = length of s and m = length of p

Solution

1. Step 1: Analyze the main loop over string s

   The algorithm slides a window of size m = len(p) over s once, performing O(1) updates per step.

2. Step 2: Consider frequency array operations

   Frequency arrays are fixed size 26, so comparisons and updates are O(1) per iteration, not dependent on m.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window with fixed alphabet size -> O(n) time [OK]

Hint: Fixed alphabet size means frequency ops are O(1) [OK]

Common Mistakes:

• Confusing frequency array size with input size
• Assuming nested loops cause O(n*m)
• Ignoring constant alphabet size