Sum of Subarray Minimums

▶

Steps

setup

Initialize variables

Initialize an empty stack and set the result accumulator to zero. Determine the length of the input array.

💡 Setting up these variables is essential to start the iteration and keep track of indices and the running sum.

Line:

stack = []
result = 0
n = len(arr)

💡 We have a clean slate to begin processing the array elements.

traverse

Start iteration with i=0, current=3

Begin iterating over the array at index 0 with current element 3. Stack is empty, so no popping occurs.

💡 First element always gets pushed because stack is empty, establishing the monotonic stack.

Line:

for i in range(n + 1):
    current = arr[i] if i < n else 0
    while stack and (i == n or current < arr[stack[-1]]):
        ...
    stack.append(i)

💡 Stack now holds index 0, representing element 3 as a candidate minimum.

compare

Move to i=1, current=1; compare with top of stack

At index 1, current element is 1, which is less than element at stack top (arr[0] = 3). This triggers popping from the stack.

💡 Finding a smaller element means we can calculate contributions for elements larger than current.

Line:

while stack and current < arr[stack[-1]]:
    mid = stack.pop()

💡 We identify that element 3's subarrays end before index 1, so we calculate its contribution now.

prune

Calculate contribution for popped index 0 (value 3)

After popping index 0, calculate left boundary as -1 (stack empty). Contribution = 3 * (0 - (-1)) * (1 - 0) = 3 * 1 * 1 = 3.

💡 Contribution counts how many subarrays have arr[0] as minimum, using distances to boundaries.

Line:

left = stack[-1] if stack else -1
count = (mid - left) * (i - mid)
result = (result + arr[mid] * count) % MOD

💡 This step shows how the algorithm counts subarrays where 3 is the minimum.

push

Push index 1 (value 1) onto stack

After processing pops, push current index 1 onto stack. Stack now contains [1].

💡 Pushing index 1 maintains the monotonic increasing stack property.

Line:

stack.append(i)

💡 Stack now holds index 1 representing element 1 as the new candidate minimum.

compare

Move to i=2, current=2; compare with top of stack

At index 2, current element 2 is greater than element at stack top (arr[1] = 1), so no popping occurs.

💡 When current element is not smaller, we simply push the index to keep stack monotonic.

Line:

while stack and current < arr[stack[-1]]:
    ...
stack.append(i)

💡 Stack remains monotonic increasing with indices [1, 2].

compare

Move to i=3, current=4; compare with top of stack

At index 3, current element 4 is greater than element at stack top (arr[2] = 2), so no popping occurs.

💡 Again, we push the index to maintain the monotonic stack.

Line:

while stack and current < arr[stack[-1]]:
    ...
stack.append(i)

💡 Stack now holds indices [1, 2, 3], representing elements [1, 2, 4].

prune

Move to sentinel i=4, current=0; trigger pops

At sentinel index 4, current element is 0, smaller than top of stack element 4, so we pop index 3.

💡 Sentinel ensures all remaining elements are processed by forcing pops.

Line:

while stack and (i == n or current < arr[stack[-1]]):
    mid = stack.pop()

💡 We start finalizing contributions for remaining elements.

prune

Calculate contribution for popped index 3 (value 4)

Calculate left boundary as 2 (top of stack). Contribution = 4 * (3 - 2) * (4 - 3) = 4 * 1 * 1 = 4.

💡 Contribution counts subarrays where 4 is minimum, bounded by indices 2 and 4.

Line:

left = stack[-1] if stack else -1
count = (mid - left) * (i - mid)
result = (result + arr[mid] * count) % MOD

💡 This step finalizes contribution for element 4.

prune

Pop index 2 (value 2) due to sentinel

Current element 0 is less than arr[2] = 2, so pop index 2 from stack.

💡 Continuing to pop elements larger than sentinel value 0.

Line:

while stack and (i == n or current < arr[stack[-1]]):
    mid = stack.pop()

💡 We process element 2's contribution now.

prune

Calculate contribution for popped index 2 (value 2)

Left boundary is 1 (top of stack). Contribution = 2 * (2 - 1) * (4 - 2) = 2 * 1 * 2 = 4.

💡 Contribution counts subarrays where 2 is minimum, bounded by indices 1 and 4.

Line:

left = stack[-1] if stack else -1
count = (mid - left) * (i - mid)
result = (result + arr[mid] * count) % MOD

💡 This step adds contribution for element 2.

prune

Pop index 1 (value 1) due to sentinel

Current element 0 is less than arr[1] = 1, so pop index 1 from stack.

💡 Final pop triggered by sentinel to process the smallest element.

Line:

while stack and (i == n or current < arr[stack[-1]]):
    mid = stack.pop()

💡 We finalize contribution for element 1.

prune

Calculate contribution for popped index 1 (value 1)

Left boundary is -1 (stack empty). Contribution = 1 * (1 - (-1)) * (4 - 1) = 1 * 2 * 3 = 6.

💡 This large contribution reflects how many subarrays have 1 as minimum.

Line:

left = stack[-1] if stack else -1
count = (mid - left) * (i - mid)
result = (result + arr[mid] * count) % MOD

💡 This step shows how the smallest element contributes to many subarrays.

push

Push sentinel index 4 (value 0) onto stack

After popping all larger elements, push sentinel index 4 onto stack.

💡 Pushing sentinel index ensures stack is not empty and loop ends cleanly.

Line:

stack.append(i)

💡 Stack now contains sentinel index, marking end of processing.

reconstruct

End of iteration, return result

All elements processed, return the accumulated result modulo 10^9+7, which is 17.

💡 Final result is sum of all subarray minimum contributions.

Line:

return result

💡 The algorithm efficiently computed the sum without enumerating all subarrays.

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    stack = []  # STEP 1: Initialize empty stack
    result = 0  # STEP 1: Initialize result accumulator
    n = len(arr)  # STEP 1: Length of array
    for i in range(n + 1):  # STEP 2-15: Iterate including sentinel
        current = arr[i] if i < n else 0  # STEP 2,8,14: Current element or sentinel
        while stack and (i == n or current < arr[stack[-1]]):  # STEP 3,8,10,12: Pop while current smaller
            mid = stack.pop()  # STEP 3,8,10,12: Pop top index
            left = stack[-1] if stack else -1  # STEP 4,9,11,13: Left boundary
            count = (mid - left) * (i - mid)  # STEP 4,9,11,13: Count subarrays
            result = (result + arr[mid] * count) % MOD  # STEP 4,9,11,13: Add contribution
        stack.append(i)  # STEP 2,5,6,7,14: Push current index
    return result  # STEP 15: Return final result

if __name__ == '__main__':
    print(sumSubarrayMins([3,1,2,4]))  # Expected output: 17

📊

Sum of Subarray Minimums - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation reveals how the stack maintains a strictly increasing order and how contributions to the result are computed exactly when a smaller element is found.

no_op

Stack (top→bottom)

empty

pushElement[0]: 3

Stack (top→bottom)

0

↑ pushed: 0

popElement[1]: 1

Stack (top→bottom)

empty

↓ popped: [0]

no_opElement[1]: 1

Stack (top→bottom)

empty

Contributes: 3

pushElement[1]: 1

Stack (top→bottom)

1

↑ pushed: 1

pushElement[2]: 2

Stack (top→bottom)

2

1

↑ pushed: 2

pushElement[3]: 4

Stack (top→bottom)

3

2

1

↑ pushed: 3

popElement[4]: 0

Stack (top→bottom)

2

1

↓ popped: [3]

no_opElement[4]: 0

Stack (top→bottom)

2

1

Contributes: 4

popElement[4]: 0

Stack (top→bottom)

1

↓ popped: [2]

no_opElement[4]: 0

Stack (top→bottom)

1

Contributes: 4

popElement[4]: 0

Stack (top→bottom)

empty

↓ popped: [1]

no_opElement[4]: 0

Stack (top→bottom)

empty

Contributes: 6

pushElement[4]: 0

Stack (top→bottom)

4

↑ pushed: 4

no_opElement[4]: 0

Stack (top→bottom)

4

Contributes: 17

Key Takeaways

✓ The monotonic stack efficiently identifies boundaries for subarray minimums without enumerating all subarrays.

This insight is hard to see from code alone because the stack operations abstract away the explicit subarray enumeration.

✓ Each popped element's contribution is computed using distances to the previous smaller element and the current index, counting subarrays where it is minimum.

Understanding how these boundaries translate to counts is easier when watching the step-by-step calculation.

✓ The sentinel element (0) at the end triggers popping all remaining elements, ensuring all contributions are accounted for.

This final step is subtle in code but critical; the visualization clarifies why the sentinel is needed.

Practice

1. Given the following Python code for checking valid parentheses, what is the return value when the input string is "([)]"?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

easy

A. False

B. True

C. Raises an exception

D. Depends on input length

Solution

1. Step 1: Trace input "([)]" through the code

   Push '(' then push '['. Next char is ')', expected to match '[' but pairs[')'] = '(', top of stack is '[' -> mismatch -> return False immediately.

2. Step 2: Confirm final output

   Function returns False as soon as mismatch is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mismatch detected at third character -> returns False [OK]

Hint: Mismatch causes immediate False return [OK]

Common Mistakes:

• Assuming order doesn't matter and returning True incorrectly

2. Consider the following buggy code snippet for the optimal calculator. Which line contains the subtle bug that causes incorrect results for expressions with negative division?

medium

A. Line with 'current_op = c' updating the operator

B. Line with 'last_num = last_num // current_num' (integer division without handling negatives)

C. Line with 'current_num = current_num * 10 + int(c)' parsing digits

D. Line with 'total += last_num' inside '+' case

Solution

1. Step 1: Identify division handling

   Integer division of negative numbers must truncate toward zero, not floor.

2. Step 2: Locate bug line

   The line 'last_num = last_num // current_num' does not handle negative last_num correctly, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct negative division requires special handling, missing here [OK]

Hint: Negative division truncation requires special code [OK]

Common Mistakes:

• Ignoring negative division truncation
• Forgetting to add last_num at end
• Misparsing digits

3. What is the time complexity of the optimal iterative stack-based algorithm to evaluate a Reverse Polish Notation expression with n tokens?

medium

A. O(n) because each token is processed exactly once with constant-time stack operations

B. O(n) for processing tokens plus O(n) for recursion stack space

C. O(n log n) due to sorting or priority queue operations involved

D. O(n^2) because each operator requires scanning the stack to find operands

Solution

1. Step 1: Identify operations per token

   Each token is processed once; operands are pushed, operators pop two operands and push one result.

2. Step 2: Analyze stack operations

   Stack push/pop are O(1), so total time is proportional to number of tokens n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No nested loops or recursion in iterative approach [OK]

Hint: Stack operations are O(1), so linear time overall [OK]

Common Mistakes:

• Assuming O(n^2) due to repeated stack scans
• Confusing recursion stack space with time
• Thinking sorting is involved

4. Suppose the calculator must now support expressions where numbers can be reused multiple times (e.g., "2*2*2") and the input length can be very large. Which modification to the optimal approach is necessary to handle this efficiently?

hard

A. Switch to a brute force left-to-right evaluation ignoring precedence to reduce complexity.

B. Implement memoization to cache results of subexpressions to avoid recomputation.

C. Use a stack to immediately evaluate multiplication and division, but keep track of last_num to handle repeated operations efficiently.

D. Use recursion with backtracking to explore all possible reuse combinations.

Solution

1. Step 1: Understand reuse impact

   Repeated multiplication/division requires immediate evaluation to maintain precedence and efficiency.

2. Step 2: Identify suitable approach

   Using a stack or stack-like variables to immediately compute * and / handles repeated operations efficiently without extra overhead.

3. Step 3: Reject alternatives

   Brute force ignores precedence, memoization is unnecessary for linear evaluation, recursion/backtracking is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Immediate evaluation with stack variables handles reuse and large inputs efficiently [OK]

Hint: Immediate evaluation with stack variables handles repeated ops efficiently [OK]

Common Mistakes:

• Ignoring precedence in reuse
• Using recursion unnecessarily
• Trying brute force for efficiency

5. Suppose the calculator expression can contain multiplication '*' and division '/' operators in addition to plus, minus, and parentheses. Which modification to the stack-based approach correctly handles operator precedence and parentheses?

hard

A. Use two stacks: one for numbers and one for operators, applying operators with higher precedence immediately before pushing lower precedence operators

B. Continue using a single stack and apply all operators in the order they appear, ignoring precedence

C. Convert the expression to postfix notation first, then evaluate using a stack

D. Evaluate recursively without any stack, relying on Python's eval() function

Solution

1. Step 1: Understand operator precedence

   Multiplication and division have higher precedence than addition and subtraction, so evaluation order matters.

2. Step 2: Modify stack approach

   Using two stacks (numbers and operators) allows applying higher precedence operators immediately, preserving correct order.

3. Step 3: Why other options fail

   Single stack ignoring precedence leads to wrong results; postfix conversion is valid but more complex; relying on eval() is unsafe and not interview-appropriate.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two-stack approach is standard for precedence and parentheses [OK]

Hint: Two stacks handle precedence and parentheses correctly [OK]

Common Mistakes:

• Ignoring precedence or relying on single stack only