Sum of Subarray Minimums

📋

Problem

Imagine you want to analyze the minimum temperature over every possible period in a month to understand cold spells better.

Given an array of integers arr, find the sum of the minimum value of every contiguous subarray of arr. Since the answer may be large, return it modulo 10^9 + 7.

1 ≤ arr.length ≤ 10^51 ≤ arr[i] ≤ 10^9

Edge cases: Single element array → output is the element itselfAll elements equal → output is element * number of subarraysStrictly increasing array → minimums are always the leftmost element in subarrays

</>

IDE

def sumSubarrayMins(arr: list[int]) -> int:public int sumSubarrayMins(int[] arr)int sumSubarrayMins(vector<int>& arr)function sumSubarrayMins(arr)

def sumSubarrayMins(arr):
    # Write your solution here
    pass

class Solution {
    public int sumSubarrayMins(int[] arr) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int sumSubarrayMins(vector<int>& arr) {
    // Write your solution here
    return 0;
}

function sumSubarrayMins(arr) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong sum due to missing moduloNot applying modulo 10^9+7 on intermediate or final sums causing overflow.✅ Apply modulo after every addition: total = (total + contribution) % MOD.

Wrong: Incorrect sum due to wrong boundary indicesIncorrect calculation of previous less or next less element indices, off-by-one errors.✅ Use monotonic stack to find indices correctly; left boundary is previous less index, right boundary is next less index.

Wrong: Wrong sum due to mishandling equal elementsUsing < instead of <= or vice versa inconsistently in stack comparisons causing wrong boundaries.✅ Decide on strict less (<) or less or equal (<=) consistently for previous and next less elements in stack.

Wrong: TLE on large inputUsing brute force O(n^2) approach instead of O(n) monotonic stack.✅ Implement monotonic stack to find previous and next less elements in O(n) time.

✓

Test Cases

Focus on handling arrays with minimal or maximal length and duplicates.

Test your monotonic stack logic on tricky sequences with duplicates and alternating minima.

Optimize your solution to linear time using monotonic stack to handle large inputs.

t1_01basic

Input{"arr":[3,1,2,4]}

Expected17

⏱ Performance - must finish in 2000ms

Subarrays and their minimums: [3]=3, [3,1]=1, [3,1,2]=1, [3,1,2,4]=1, [1]=1, [1,2]=1, [1,2,4]=1, [2]=2, [2,4]=2, [4]=4. Sum=17.

💡 Consider all contiguous subarrays and find their minimums.

💡 Use a monotonic stack to find previous and next less elements efficiently.

💡 Calculate contribution of each element as minimum using left and right boundaries.

Why it failed: Incorrect sum for canonical example; likely missing modulo or incorrect boundaries calculation. Fix by correctly computing left/right less indices and applying modulo.

✓ Correctly computes sum of subarray minimums for canonical example.

t1_02basic

Input{"arr":[11,81,94,43,3]}

Expected444

⏱ Performance - must finish in 2000ms

Sum of minimums of all subarrays computed by brute force is 444.

💡 Try brute force on small arrays to verify your approach.

💡 Check how each element contributes as minimum to subarrays using monotonic stack.

💡 Use previous less and next less element indices to calculate contribution.

Why it failed: Wrong output indicates incorrect contribution calculation or boundary indices. Fix by ensuring correct monotonic stack logic for previous and next less elements.

✓ Correctly handles different input with varied values.

t2_01edge

Input{"arr":[5]}

Expected5

⏱ Performance - must finish in 2000ms

Single element array; sum of minimums is the element itself.

💡 Check behavior when array length is 1.

💡 Ensure code handles single element without errors.

💡 Return the element value modulo 10^9+7.

Why it failed: Fails single element case; likely indexing or empty stack errors. Fix by handling n=1 case properly and returning arr[0] % MOD.

✓ Correctly returns single element as sum.

t2_02edge

Input{"arr":[2,2,2,2]}

Expected20

⏱ Performance - must finish in 2000ms

All elements equal; sum = element * number of subarrays = 2 * 10 = 20.

💡 Consider how equal elements affect previous and next less elements.

💡 Check if your monotonic stack treats equal elements correctly (strictly less vs less or equal).

💡 Use <= or < consistently to handle duplicates in stack.

Why it failed: Incorrect output due to wrong handling of equal elements in stack. Fix by using strict less (<) or less or equal (<=) consistently in monotonic stack comparisons.

✓ Handles all equal elements correctly.

t2_03edge

Input{"arr":[1,2,3,4,5]}

Expected35

⏱ Performance - must finish in 2000ms

Strictly increasing array; minimums are always leftmost elements in subarrays.

💡 Check how previous less elements behave in strictly increasing arrays.

💡 Verify that next less elements are correctly identified as none or array end.

💡 Calculate contribution using boundaries correctly for increasing sequences.

Why it failed: Fails strictly increasing case; likely incorrect next less element logic. Fix by correctly identifying next less elements as array length when none found.

✓ Correctly computes sum for strictly increasing array.

t3_01corner

Input{"arr":[5,4,3,2,1]}

Expected35

⏱ Performance - must finish in 2000ms

Strictly decreasing array; minimums are always rightmost elements in subarrays.

💡 Check how previous less and next less elements behave in strictly decreasing arrays.

💡 Verify that previous less elements are none or array start.

💡 Calculate contribution using boundaries correctly for decreasing sequences.

Why it failed: Fails strictly decreasing case; likely reversed boundary calculation or off-by-one error. Fix by correctly computing left and right boundaries for previous and next less elements.

✓ Correctly computes sum for strictly decreasing array.

t3_02corner

Input{"arr":[3,1,3,1,3]}

Expected21

⏱ Performance - must finish in 2000ms

Array with duplicates and alternating minima; tests correct handling of equal elements and boundaries.

💡 Check how equal elements are handled in monotonic stack (strictly less vs less or equal).

💡 Verify contribution calculation for elements with duplicates nearby.

💡 Ensure boundaries do not overlap incorrectly for equal elements.

Why it failed: Incorrect output due to mishandling equal elements in stack or boundaries. Fix by consistent use of < or <= in stack comparisons and boundary calculations.

✓ Correctly handles duplicates and alternating minima.

t3_03corner

Input{"arr":[2,9,7,8,3,4,6,1]}

Expected117

⏱ Performance - must finish in 2000ms

Random array testing general correctness and boundary calculations.

💡 Use monotonic stack to find previous and next less elements for each index.

💡 Calculate contribution of each element as minimum using left and right boundaries.

💡 Sum contributions modulo 10^9+7.

Why it failed: Wrong output due to incorrect boundary indices or modulo application. Fix by carefully computing boundaries and applying modulo at each addition.

✓ Correctly computes sum for random array.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, O(n) monotonic stack solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out; use O(n) monotonic stack approach.

💡 Precompute previous less and next less elements to calculate contributions.

💡 Avoid nested loops; use stack to achieve linear time.

Why it failed: TLE due to O(n^2) brute force or inefficient approach. Fix by implementing O(n) monotonic stack solution.

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

Practice

1. You are given an integer array and need to determine if there exists a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force triple nested loops checking all triplets

B. Greedy approach scanning from left to right picking local minima and maxima

C. Using a monotonic stack to track potential '3' and '2' values while iterating backwards

D. Dynamic programming with prefix minimum and suffix maximum arrays

Solution

1. Step 1: Understand the 132 pattern condition

   The problem requires finding a subsequence i < j < k with nums[i] < nums[k] < nums[j], which is the 132 pattern.

2. Step 2: Identify the approach that achieves O(n) time

   The monotonic stack approach iterates from right to left, maintaining candidates for the '3' and '2' elements efficiently, achieving linear time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is known optimal for 132 pattern detection [OK]

Hint: Monotonic stack solves 132 pattern in O(n) [OK]

Common Mistakes:

• Thinking brute force is acceptable for large inputs
• Confusing greedy with monotonic stack
• Assuming DP is needed

2. You need to implement a data structure that supports enqueue and dequeue operations using only stack operations (push and pop). Which approach guarantees an amortized O(1) time complexity per operation?

easy

A. Use two stacks: push elements onto one stack, and pop elements from the other stack, transferring elements only when the pop stack is empty.

B. Use a single stack and recursion to simulate dequeue by popping all elements and restoring them after retrieving the front.

C. Use two stacks and transfer elements from push stack to pop stack on every push operation to keep pop stack always ready.

D. Use a queue internally and simulate stacks by reversing the order on every operation.

Solution

1. Step 1: Understand the problem constraints

   The goal is to implement a queue using stacks with efficient enqueue and dequeue operations.

2. Step 2: Analyze approaches for efficiency

   Approach A uses two stacks and transfers elements only when the pop stack is empty, achieving amortized O(1) per operation. Approach B uses recursion and is O(n) per pop. Approach C transfers on every push, causing O(n) per push. Approach D is unrelated and inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two stacks with lazy transfer -> amortized O(1) [OK]

Hint: Two stacks with lazy transfer gives amortized O(1) [OK]

Common Mistakes:

• Thinking transferring on every push is optimal
• Using recursion causing O(n) pop

3. Consider the following Python code implementing the two-pass counter approach for longest valid parentheses. What is the final returned value when the input string is "(()"?

def longestValidParentheses(s: str) -> int:
    left = right = max_len = 0
    # Left to right scan
    for ch in s:
        if ch == '(': left += 1
        else: right += 1
        if left == right:
            max_len = max(max_len, 2 * right)
        elif right > left:
            left = right = 0
    left = right = 0
    # Right to left scan
    for ch in reversed(s):
        if ch == ')': right += 1
        else: left += 1
        if left == right:
            max_len = max(max_len, 2 * left)
        elif left > right:
            left = right = 0
    return max_len

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace left to right scan for input "(()"

   Characters: '(', '(', ')' - left=1, right=0 - left=2, right=0 - left=2, right=1 No reset since right < left; max_len updated only when left==right (never here)

2. Step 2: Trace right to left scan

   Characters reversed: ')', '(', '(' - right=1, left=0 - right=1, left=1 -> left==right, max_len = max(0, 2*1) = 2 - right=1, left=2 -> left > right, reset left=right=0 Return max_len = 2

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest valid substring is "()" with length 2 [OK]

Hint: Two-pass scan finds max length 2 for "(()" [OK]

Common Mistakes:

• Confusing max_len update condition
• Forgetting right to left scan resets
• Off-by-one counting

4. Consider the following buggy code for finding the first unique character in a stream. Which line contains the subtle bug that causes incorrect output when duplicates appear?

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26
    q = deque()
    result = []
    for ch in stream:
        idx = ord(ch) - ord('a')
        freq[idx] += 1
        if freq[idx] == 1:
            q.append(ch)
        # BUG: Missing removal of duplicates from queue front
        result.append(q[0] if q else '#')
    return result

medium

A. Line where freq[idx] is incremented

B. Line where character is appended to queue

C. Line where result is appended

D. Line where duplicates are removed from queue front (missing here)

Solution

1. Step 1: Identify missing logic

   The code does not remove characters from the queue front when their frequency exceeds 1.

2. Step 2: Understand impact

   Without popping duplicates, the queue front may be a repeated character, causing wrong first unique output.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing while loop to pop duplicates is the bug [OK]

Hint: Always remove duplicates from queue front to maintain correctness [OK]

Common Mistakes:

• Forgetting to pop duplicates from queue front
• Appending duplicates multiple times
• Not handling empty queue case

5. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character might be compared multiple times during matching

B. O(n) because each character is processed once with constant-time stack operations

C. O(n log n) due to sorting or ordering operations on the stack

D. O(n) for time but O(n^2) for space due to stack growth in worst case

Solution

1. Step 1: Identify complexity of outer loop

   The algorithm iterates over each character exactly once, so the loop is O(n).

2. Step 2: Check stack operations

   Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant-time stack ops -> O(n) time [OK]

Hint: Each character processed once with O(1) stack ops [OK]

Common Mistakes:

• Confusing with brute force O(n^2) approach