Number of Subarrays with Bounded Maximum

▶

Steps

setup

Initialize countAtMost for bound = right (3)

Start counting subarrays with max ≤ 3. Initialize count and length to 0 before processing any elements.

💡 Initializing counters is essential to accumulate valid subarrays as we iterate.

Line:

def countAtMost(nums, bound):
    count = 0
    length = 0

💡 We track two variables: 'count' accumulates total valid subarrays, 'length' tracks current valid subarray length.

fill_cells

Process first number 2 (≤ 3) for countAtMost(right)

Check if 2 ≤ 3. It is, so increase length to 1 and add length to count (count=1).

💡 When current number is within bound, extend current valid subarray and add its length to total count.

Line:

for num in nums:
    if num <= bound:
        length += 1
        count += length

💡 Each valid number extends the subarray, increasing the count of valid subarrays ending at this index.

fill_cells

Process second number 1 (≤ 3) for countAtMost(right)

1 ≤ 3, so increase length to 2 and add length to count (count=3).

💡 Continuing valid subarray, length grows and count accumulates all subarrays ending here.

Line:

if num <= bound:
    length += 1
    count += length

💡 Subarrays ending at this index include [1] and [2,1], total 2 new subarrays added.

fill_cells

Process third number 4 (> 3) for countAtMost(right)

4 > 3, so reset length to 0; no new valid subarrays end here.

💡 A number exceeding bound breaks the current valid subarray sequence.

Line:

else:
    length = 0

💡 Resetting length means no valid subarrays can end at this element.

fill_cells

Process fourth number 3 (≤ 3) for countAtMost(right)

3 ≤ 3, so length becomes 1 and count increases by 1 (count=4).

💡 After reset, a valid number restarts the count of valid subarrays.

Line:

if num <= bound:
    length += 1
    count += length

💡 Counting subarrays ending at this element restarts after invalid break.

fill_row

Finish countAtMost(right) and store result

All elements processed for bound=3; total count is 4.

💡 This count includes all subarrays with max ≤ 3.

Line:

return count

💡 Counting subarrays with max ≤ right is complete and stored for later subtraction.

setup

Initialize countAtMost for bound = left - 1 (1)

Start counting subarrays with max ≤ 1. Reset count and length to 0.

💡 We repeat counting for the lower bound to subtract later.

Line:

def countAtMost(nums, bound):
    count = 0
    length = 0

💡 Resetting counters prepares for second counting phase.

fill_cells

Process first number 2 (> 1) for countAtMost(left-1)

2 > 1, so reset length to 0; no valid subarrays end here.

💡 Numbers exceeding bound break valid subarray sequences.

Line:

for num in nums:
    if num <= bound:
        length += 1
        count += length
    else:
        length = 0

💡 No subarrays with max ≤ 1 can include 2.

fill_cells

Process second number 1 (≤ 1) for countAtMost(left-1)

1 ≤ 1, increase length to 1 and add to count (count=1).

💡 Valid number starts a new valid subarray sequence.

Line:

if num <= bound:
    length += 1
    count += length

💡 Counting subarrays ending at this element restarts after reset.

fill_cells

Process third number 4 (> 1) for countAtMost(left-1)

4 > 1, reset length to 0; no valid subarrays end here.

💡 Invalid number breaks current valid subarray sequence.

Line:

else:
    length = 0

💡 Counting pauses until next valid number.

fill_cells

Process fourth number 3 (> 1) for countAtMost(left-1)

3 > 1, reset length to 0 again; no valid subarrays end here.

💡 Continued invalid numbers keep length reset.

Line:

else:
    length = 0

💡 No subarrays with max ≤ 1 include 3.

fill_row

Finish countAtMost(left-1) and store result

All elements processed for bound=1; total count is 1.

💡 This count includes all subarrays with max ≤ 1.

Line:

return count

💡 Counting subarrays with max ≤ left-1 is complete and stored.

reconstruct

Compute final answer by subtracting counts

Subtract countLeft (1) from countRight (4) to get 3, the number of subarrays with max between 2 and 3.

💡 Subtracting counts isolates subarrays with max in [left, right].

Line:

return countAtMost(nums, right) - countAtMost(nums, left - 1)

💡 Final answer is difference of two counts, representing valid subarrays in the bounded range.

reconstruct

Return final answer 3

The algorithm returns 3, the count of subarrays with max between 2 and 3.

💡 Returning the final computed result completes the algorithm.

Line:

print(numSubarrayBoundedMax([2,1,4,3], 2, 3))  # Output: 3

💡 The final output matches the expected count of valid subarrays.

def countAtMost(nums, bound):  # STEP 1,7
    count = 0  # STEP 1,7
    length = 0  # STEP 1,7
    for num in nums:  # STEP 2-5,8-11
        if num <= bound:  # STEP 2,3,5,9
            length += 1  # STEP 2,3,5,9
            count += length  # STEP 2,3,5,9
        else:  # STEP 4,8,10,11
            length = 0  # STEP 4,8,10,11
    return count  # STEP 6,12

def numSubarrayBoundedMax(nums, left, right):  # STEP 13,14
    return countAtMost(nums, right) - countAtMost(nums, left - 1)  # STEP 13

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

📊

Number of Subarrays with Bounded Maximum - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the algorithm efficiently counts subarrays without enumerating them, by tracking lengths of valid segments and accumulating counts.

initialize

count→0

length→0

bound→3

num→null

increment

count→1

length→1

bound→3

num→2

increment

count→3

length→2

bound→3

num→1

reset

count→3

length→0

bound→3

num→4

increment

count→4

length→1

bound→3

num→3

return

countRight→4

Result: 4

initialize

count→0

length→0

bound→1

num→null

reset

count→0

length→0

bound→1

num→2

increment

count→1

length→1

bound→1

num→1

reset

count→1

length→0

bound→1

num→4

reset

count→1

length→0

bound→1

num→3

return

countLeft→1

countRight→4

update

countRight→4

countLeft→1

Result: 3

return

answer→3

Result: 3

Key Takeaways

✓ The algorithm counts subarrays with max ≤ bound by tracking lengths of valid subarrays ending at each element.

This insight is hard to see from code alone because the cumulative counting logic is subtle and not explicit about subarray enumeration.

✓ Subtracting counts for bounds right and left-1 isolates subarrays with max in the desired range efficiently.

Understanding this subtraction trick is easier when watching the two counting sequences side-by-side.

✓ Resetting length to zero on invalid elements breaks subarray sequences, which is crucial for correct counting.

Seeing the reset visually clarifies why invalid elements prevent counting and how the algorithm restarts counting after them.

Practice

1. Consider the following Python function that returns the maximum number of pairs summing to k. What is the returned value when calling maxOperations([1, 2, 3, 4], 5)?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace iterations for input [1, 2, 3, 4], k=5

   Iteration 1: num=1, complement=4, freq empty -> freq[1]=1
   Iteration 2: num=2, complement=3, freq={1:1} -> freq[2]=1
   Iteration 3: num=3, complement=2, freq[2]=1 > 0 -> count=1, freq[2]=0
   Iteration 4: num=4, complement=1, freq[1]=1 > 0 -> count=2, freq[1]=0

2. Step 2: Final count returned

   Count is 2 after processing all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pairs (1,4) and (2,3) sum to 5 [OK]

Hint: Pairs (1,4) and (2,3) found -> count 2 [OK]

Common Mistakes:

• Counting pairs multiple times
• Off-by-one in frequency decrement
• Confusing complement logic

2. The following code attempts to find the pivot index but contains a subtle bug. Which line contains the bug?

def pivotIndex(nums):
    total = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total - left_sum:
            return i
        left_sum += num
    return -1

medium

A. Line 6: left_sum += num

B. Line 4: for i, num in enumerate(nums):

C. Line 2: total = sum(nums)

D. Line 5: if left_sum == total - left_sum:

Solution

1. Step 1: Understand the condition

   The condition should check if left_sum equals right sum, which is total - left_sum - current num.

2. Step 2: Identify the bug

   The code incorrectly checks if left_sum == total - left_sum, missing subtracting the current num, causing wrong pivot detection.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct condition is left_sum == total - left_sum - num [OK]

Hint: Check if right sum calculation includes current element [OK]

Common Mistakes:

• Forgetting to subtract current num from total
• Misplacing sum updates
• Returning null instead of -1

3. Consider the following buggy code for finding the longest substring with at most two distinct characters. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line inside while loop missing check to decrement distinct_count when freq hits zero

B. Line where freq[ord(s[right])] is incremented

C. Line inside while loop where freq[ord(s[left])] is decremented

D. Line where distinct_count is incremented when freq is zero

Solution

1. Step 1: Identify the bug

   The code decrements freq for s[left] inside the while loop but does not check if freq reaches zero to decrement distinct_count.

2. Step 2: Consequences of missing check

   Without decrementing distinct_count, the while loop condition distinct_count > 2 never becomes false, causing infinite loop or incorrect window size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing distinct_count decrement inside while loop is a classic subtle bug [OK]

Hint: Check distinct_count update when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement distinct_count
• Incorrect window size calculation
• Not breaking early in brute force

4. What is the time complexity of the optimal sliding window solution for the Minimum Operations to Reduce X to Zero problem, assuming the input array length is n?

medium

A. O(n^2) due to nested loops for adjusting window boundaries.

B. O(n) for the main loop plus O(n) for sum computations inside the loop.

C. O(n) because each element is visited at most twice by left and right pointers.

D. O(n log n) due to sorting or binary search steps.

Solution

1. Step 1: Analyze the main loop and window adjustments

   The right pointer moves from 0 to n-1 once, and the left pointer only moves forward when shrinking the window, so each element is visited at most twice.

2. Step 2: Confirm no nested loops causing quadratic time

   While loop inside the for loop advances left pointer without resetting, so total moves of left pointer ≤ n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window runs in linear time [OK]

Hint: Sliding window moves pointers linearly [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Forgetting that left pointer only moves forward
• Confusing sum computations as extra loops

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