Sum of Subarray Minimums

🎯

Sum of Subarray Minimums

mediumSTACKAmazonGoogleFacebook

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

💡 This problem asks for the sum of minimum values over all contiguous subarrays. Beginners often struggle because enumerating all subarrays naively is too slow, and understanding how to efficiently count contributions of each element requires a new perspective using stacks.

📋

Problem Statement

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

💡

Example

Input"[3,1,2,4]"

Output17

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 = 3+1+1+1+1+1+1+2+2+4 = 17.

• Single element array → output is the element itself
• All elements equal → output is element * number of subarrays
• Strictly increasing array → minimums are always the leftmost element in subarrays
• Strictly decreasing array → minimums are always the rightmost element in subarrays

⚠️

Common Mistakes

Using '>' instead of '>=' when finding next less element

Incorrect boundaries leading to wrong counts and wrong final sum

✅ Use '>=' for next less to handle duplicates correctly

Not using modulo operation after each addition

Integer overflow causing wrong answers or runtime errors

✅ Apply modulo after every addition and multiplication

Forgetting to add sentinel element at the end

Some elements remain in stack and their contributions are never counted

✅ Add a sentinel iteration with value smaller than all elements to flush stack

Mixing up previous less and next less boundaries

Incorrect calculation of subarray counts leading to wrong sum

✅ Carefully define prevLess as strictly less to the left and nextLess as strictly less to the right

Using nested loops to find minimum inside brute force

O(n^3) time complexity causing immediate TLE

✅ Update minimum on the fly inside inner loop to achieve O(n^2)

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by explicitly enumerating all subarrays and their minimums, though it is inefficient.

Intuition

Check every possible subarray, find its minimum, and add it to the sum.

Algorithm

1. Initialize sum to 0.
2. For each start index i in the array:
3. For each end index j from i to end:
4. Find the minimum element in arr[i..j].
5. Add this minimum to sum.
6. Return sum modulo 10^9+7.

💡 The nested loops and repeated minimum search make this approach straightforward but slow and hard to optimize directly.

</>

Code

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    total = 0
    for i in range(n):
        current_min = arr[i]
        for j in range(i, n):
            if arr[j] < current_min:
                current_min = arr[j]
            total = (total + current_min) % MOD
    return total

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

Line Notes

MOD = 10**9 + 7Defines the modulo to keep the result within integer limits and prevent overflow.

for i in range(n):Outer loop selects the start index of subarrays to consider all possible subarrays.

current_min = arr[i]Initialize minimum for the current subarray starting at index i.

for j in range(i, n):Inner loop extends the subarray to the right, covering all subarrays starting at i.

if arr[j] < current_min:Update minimum if a smaller element is found in the current subarray.

total = (total + current_min) % MODAdd current minimum to total with modulo to keep result within bounds.

import java.util.*;
public class Solution {
    public static int sumSubarrayMins(int[] arr) {
        int MOD = 1000000007;
        int n = arr.length;
        long total = 0;
        for (int i = 0; i < n; i++) {
            int currentMin = arr[i];
            for (int j = i; j < n; j++) {
                if (arr[j] < currentMin) {
                    currentMin = arr[j];
                }
                total = (total + currentMin) % MOD;
            }
        }
        return (int) total;
    }

    public static void main(String[] args) {
        System.out.println(sumSubarrayMins(new int[]{3,1,2,4})); // Expected: 17
    }
}

Line Notes

int MOD = 1000000007;Modulo constant to prevent integer overflow and keep results within limits.

for (int i = 0; i < n; i++) {Outer loop picks subarray start index to cover all subarrays.

int currentMin = arr[i];Initialize minimum for the current subarray starting at i.

for (int j = i; j < n; j++) {Inner loop extends subarray to the right.

if (arr[j] < currentMin) {Update minimum if smaller element found in current subarray.

total = (total + currentMin) % MOD;Add minimum to total with modulo to avoid overflow.

#include <iostream>
#include <vector>
using namespace std;

int sumSubarrayMins(vector<int>& arr) {
    const int MOD = 1000000007;
    int n = arr.size();
    long long total = 0;
    for (int i = 0; i < n; i++) {
        int currentMin = arr[i];
        for (int j = i; j < n; j++) {
            if (arr[j] < currentMin) {
                currentMin = arr[j];
            }
            total = (total + currentMin) % MOD;
        }
    }
    return (int)total;
}

int main() {
    vector<int> arr = {3,1,2,4};
    cout << sumSubarrayMins(arr) << endl; // Expected: 17
    return 0;
}

Line Notes

const int MOD = 1000000007;Modulo constant to keep results within bounds and prevent overflow.

for (int i = 0; i < n; i++) {Outer loop selects subarray start index.

int currentMin = arr[i];Initialize minimum for current subarray starting at i.

for (int j = i; j < n; j++) {Inner loop extends subarray to the right.

if (arr[j] < currentMin) {Update minimum if smaller element found.

total = (total + currentMin) % MOD;Add minimum to total with modulo.

function sumSubarrayMins(arr) {
    const MOD = 1000000007;
    const n = arr.length;
    let total = 0;
    for (let i = 0; i < n; i++) {
        let currentMin = arr[i];
        for (let j = i; j < n; j++) {
            if (arr[j] < currentMin) {
                currentMin = arr[j];
            }
            total = (total + currentMin) % MOD;
        }
    }
    return total;
}

// Test
console.log(sumSubarrayMins([3,1,2,4])); // Expected: 17

Line Notes

const MOD = 1000000007;Modulo to keep sum within integer limits and prevent overflow.

for (let i = 0; i < n; i++) {Outer loop picks subarray start index.

let currentMin = arr[i];Initialize minimum for current subarray starting at i.

for (let j = i; j < n; j++) {Inner loop extends subarray to the right.

if (arr[j] < currentMin) {Update minimum if smaller element found.

total = (total + currentMin) % MOD;Add current minimum to total with modulo.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops iterate over all subarrays, and minimum is updated in O(1) inside inner loop, resulting in O(n^2) time.

💡 For n=20, this means about 400 operations, which is manageable, but for n=10^5, it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem and motivate better solutions.

🧠

Using Previous Less Element and Next Less Element (Monotonic Stack)

💡 This approach introduces the key insight that each element's contribution to the sum can be counted by knowing how far it extends as the minimum to the left and right, which can be found efficiently using monotonic stacks.

Intuition

For each element, find the distance to the previous smaller element and the next smaller element. The element contributes its value multiplied by the number of subarrays where it is the minimum.

Algorithm

1. Initialize two arrays: prevLess and nextLess to store indices of previous and next smaller elements.
2. Use a monotonic increasing stack to fill prevLess by scanning left to right.
3. Use a monotonic increasing stack to fill nextLess by scanning right to left.
4. For each element, calculate contribution = arr[i] * (i - prevLess[i]) * (nextLess[i] - i).
5. Sum all contributions modulo 10^9+7 and return.

💡 The key is to understand how the product of distances counts the number of subarrays where the element is minimum.

</>

Code

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    stack = []
    prevLess = [-1] * n
    nextLess = [n] * n

    # Find previous less element for each index
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        prevLess[i] = stack[-1] if stack else -1
        stack.append(i)

    stack.clear()
    # Find next less element for each index
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        nextLess[i] = stack[-1] if stack else n
        stack.append(i)

    result = 0
    for i in range(n):
        left_count = i - prevLess[i]
        right_count = nextLess[i] - i
        result = (result + arr[i] * left_count * right_count) % MOD
    return result

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

Line Notes

prevLess = [-1] * nInitialize with -1 meaning no smaller element to the left, setting boundary for counting.

while stack and arr[stack[-1]] > arr[i]:Pop indices with values greater than current to maintain monotonic increasing stack for previous less.

prevLess[i] = stack[-1] if stack else -1Assign previous less index or -1 if none found.

stack.clear()Reset stack to reuse for next less calculation scanning from right.

while stack and arr[stack[-1]] >= arr[i]:Pop indices with values greater or equal to current for next less to handle duplicates correctly.

result = (result + arr[i] * left_count * right_count) % MODAdd contribution of current element to total modulo to avoid overflow.

import java.util.*;
public class Solution {
    public static int sumSubarrayMins(int[] arr) {
        int MOD = 1000000007;
        int n = arr.length;
        int[] prevLess = new int[n];
        int[] nextLess = new int[n];
        Arrays.fill(prevLess, -1);
        Arrays.fill(nextLess, n);
        Deque<Integer> stack = new ArrayDeque<>();

        // Previous less
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            prevLess[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();
        // Next less
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            nextLess[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long result = 0;
        for (int i = 0; i < n; i++) {
            long leftCount = i - prevLess[i];
            long rightCount = nextLess[i] - i;
            result = (result + (long)arr[i] * leftCount * rightCount) % MOD;
        }
        return (int)result;
    }

    public static void main(String[] args) {
        System.out.println(sumSubarrayMins(new int[]{3,1,2,4})); // Expected: 17
    }
}

Line Notes

Arrays.fill(prevLess, -1);Initialize previous less indices to -1 meaning no smaller element to the left.

while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {Pop indices with values greater than current to maintain monotonic increasing stack.

prevLess[i] = stack.isEmpty() ? -1 : stack.peek();Assign previous less index or -1 if none.

stack.clear();Clear stack to reuse for next less calculation scanning from right.

while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {Pop indices with values greater or equal to current for next less to handle duplicates.

result = (result + (long)arr[i] * leftCount * rightCount) % MOD;Add contribution of element to result modulo.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int sumSubarrayMins(vector<int>& arr) {
    const int MOD = 1000000007;
    int n = arr.size();
    vector<int> prevLess(n, -1), nextLess(n, n);
    stack<int> st;

    // Previous less
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] > arr[i]) {
            st.pop();
        }
        prevLess[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }

    // Clear stack
    while (!st.empty()) st.pop();

    // Next less
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] >= arr[i]) {
            st.pop();
        }
        nextLess[i] = st.empty() ? n : st.top();
        st.push(i);
    }

    long long result = 0;
    for (int i = 0; i < n; i++) {
        long long leftCount = i - prevLess[i];
        long long rightCount = nextLess[i] - i;
        result = (result + (long long)arr[i] * leftCount * rightCount) % MOD;
    }
    return (int)result;
}

int main() {
    vector<int> arr = {3,1,2,4};
    cout << sumSubarrayMins(arr) << endl; // Expected: 17
    return 0;
}

Line Notes

const int MOD = 1000000007;Initialize modulo constant as integer literal to avoid floating point issues.

while (!st.empty() && arr[st.top()] > arr[i]) {Pop indices with values greater than current to maintain monotonic increasing stack.

prevLess[i] = st.empty() ? -1 : st.top();Assign previous less index or -1 if none.

while (!st.empty() && arr[st.top()] >= arr[i]) {Pop indices with values greater or equal to current for next less to handle duplicates.

nextLess[i] = st.empty() ? n : st.top();Assign next less index or n if none.

result = (result + (long long)arr[i] * leftCount * rightCount) % MOD;Add contribution of element to result modulo.

function sumSubarrayMins(arr) {
    const MOD = 1000000007;
    const n = arr.length;
    const prevLess = new Array(n).fill(-1);
    const nextLess = new Array(n).fill(n);
    const stack = [];

    // Previous less
    for (let i = 0; i < n; i++) {
        while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        prevLess[i] = stack.length ? stack[stack.length - 1] : -1;
        stack.push(i);
    }

    stack.length = 0;

    // Next less
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        nextLess[i] = stack.length ? stack[stack.length - 1] : n;
        stack.push(i);
    }

    let result = 0;
    for (let i = 0; i < n; i++) {
        const leftCount = i - prevLess[i];
        const rightCount = nextLess[i] - i;
        result = (result + arr[i] * leftCount * rightCount) % MOD;
    }
    return result;
}

// Test
console.log(sumSubarrayMins([3,1,2,4])); // Expected: 17

Line Notes

const MOD = 1000000007;Initialize modulo constant as integer literal to avoid floating point issues.

while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {Pop indices with values greater than current to maintain monotonic increasing stack.

prevLess[i] = stack.length ? stack[stack.length - 1] : -1;Assign previous less index or -1 if none.

stack.length = 0;Clear stack to reuse for next less calculation scanning from right.

while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {Pop indices with values greater or equal to current for next less to handle duplicates.

result = (result + arr[i] * leftCount * rightCount) % MOD;Add contribution of element to result modulo.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is pushed and popped at most once in the monotonic stacks, so total time is linear. Extra arrays use linear space.

💡 For n=10^5, this means about 200,000 operations, which is efficient and feasible.

Interview Verdict: Accepted

This is the standard efficient solution using monotonic stacks and contribution counting.

🧠

Optimized Monotonic Stack with Single Pass

💡 This approach merges the previous less and next less computations into a single pass using a monotonic stack and calculates contributions on the fly, reducing code complexity.

Intuition

Use a stack to maintain increasing elements; when popping an element, calculate its contribution immediately using the current index and the index of the previous smaller element.

Algorithm

1. Initialize an empty stack and result = 0.
2. Iterate over array indices from 0 to n (inclusive), treating n as a sentinel index with value 0.
3. While stack is not empty and current element is less than element at stack top:
4. Pop top index from stack as 'mid'.
5. Calculate left boundary as stack top after pop or -1 if empty.
6. Calculate contribution = arr[mid] * (mid - left) * (i - mid).
7. Add contribution to result modulo 10^9+7.
8. Push current index onto stack.
9. Return result.

💡 The sentinel ensures all elements are popped by the end, and contributions are calculated exactly once.

</>

Code

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    stack = []
    result = 0
    n = len(arr)
    for i in range(n + 1):
        current = arr[i] if i < n else 0
        while stack and (i == n or current < arr[stack[-1]]):
            mid = stack.pop()
            left = stack[-1] if stack else -1
            count = (mid - left) * (i - mid)
            result = (result + arr[mid] * count) % MOD
        stack.append(i)
    return result

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

Line Notes

for i in range(n + 1):Iterate one extra time to pop all remaining elements using sentinel.

current = arr[i] if i < n else 0Use sentinel value 0 at the end to flush stack and finalize contributions.

while stack and (i == n or current < arr[stack[-1]]):Pop while current element is smaller than top of stack to maintain monotonicity.

mid = stack.pop()Pop the index of the element whose contribution is finalized now.

left = stack[-1] if stack else -1Find left boundary index or -1 if none exists.

count = (mid - left) * (i - mid)Calculate number of subarrays where arr[mid] is minimum using distances.

result = (result + arr[mid] * count) % MODAdd contribution modulo to keep result within bounds.

import java.util.*;
public class Solution {
    public static int sumSubarrayMins(int[] arr) {
        int MOD = 1000000007;
        int n = arr.length;
        Deque<Integer> stack = new ArrayDeque<>();
        long result = 0;
        for (int i = 0; i <= n; i++) {
            int current = (i < n) ? arr[i] : 0;
            while (!stack.isEmpty() && (i == n || current < arr[stack.peek()])) {
                int mid = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                long count = (long)(mid - left) * (i - mid);
                result = (result + (long)arr[mid] * count) % MOD;
            }
            stack.push(i);
        }
        return (int)result;
    }

    public static void main(String[] args) {
        System.out.println(sumSubarrayMins(new int[]{3,1,2,4})); // Expected: 17
    }
}

Line Notes

for (int i = 0; i <= n; i++) {Iterate one extra time to flush stack with sentinel value.

int current = (i < n) ? arr[i] : 0;Sentinel value 0 ensures all elements are popped and contributions counted.

while (!stack.isEmpty() && (i == n || current < arr[stack.peek()])) {Pop while current element is smaller than top of stack to maintain monotonicity.

int mid = stack.pop();Pop element whose contribution is finalized now.

int left = stack.isEmpty() ? -1 : stack.peek();Find left boundary index or -1 if none.

result = (result + (long)arr[mid] * count) % MOD;Add contribution modulo to keep result within bounds.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int sumSubarrayMins(vector<int>& arr) {
    const int MOD = 1000000007;
    int n = arr.size();
    stack<int> st;
    long long result = 0;
    for (int i = 0; i <= n; i++) {
        int current = (i < n) ? arr[i] : 0;
        while (!st.empty() && (i == n || current < arr[st.top()])) {
            int mid = st.top(); st.pop();
            int left = st.empty() ? -1 : st.top();
            long long count = (long long)(mid - left) * (i - mid);
            result = (result + (long long)arr[mid] * count) % MOD;
        }
        st.push(i);
    }
    return (int)result;
}

int main() {
    vector<int> arr = {3,1,2,4};
    cout << sumSubarrayMins(arr) << endl; // Expected: 17
    return 0;
}

Line Notes

for (int i = 0; i <= n; i++) {Loop one extra time to flush stack with sentinel value.

int current = (i < n) ? arr[i] : 0;Sentinel value 0 ensures all elements are popped and contributions counted.

while (!st.empty() && (i == n || current < arr[st.top()])) {Pop while current element is smaller than top of stack to maintain monotonicity.

int mid = st.top(); st.pop();Pop element whose contribution is finalized now.

int left = st.empty() ? -1 : st.top();Find left boundary index or -1 if none.

result = (result + (long long)arr[mid] * count) % MOD;Add contribution modulo to keep result within bounds.

function sumSubarrayMins(arr) {
    const MOD = 1000000007;
    const n = arr.length;
    const stack = [];
    let result = 0;
    for (let i = 0; i <= n; i++) {
        const current = i < n ? arr[i] : 0;
        while (stack.length && (i === n || current < arr[stack[stack.length - 1]])) {
            const mid = stack.pop();
            const left = stack.length ? stack[stack.length - 1] : -1;
            const count = (mid - left) * (i - mid);
            result = (result + arr[mid] * count) % MOD;
        }
        stack.push(i);
    }
    return result;
}

// Test
console.log(sumSubarrayMins([3,1,2,4])); // Expected: 17

Line Notes

for (let i = 0; i <= n; i++) {Iterate one extra time to flush stack with sentinel value.

const current = i < n ? arr[i] : 0;Sentinel value 0 ensures all elements are popped and contributions counted.

while (stack.length && (i === n || current < arr[stack[stack.length - 1]])) {Pop while current element is smaller than top of stack to maintain monotonicity.

const mid = stack.pop();Pop element whose contribution is finalized now.

const left = stack.length ? stack[stack.length - 1] : -1;Find left boundary index or -1 if none.

result = (result + arr[mid] * count) % MOD;Add contribution modulo to keep result within bounds.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is pushed and popped once, so linear time and space.

💡 This approach is both efficient and concise, ideal for large inputs.

Interview Verdict: Accepted

This is a clean and optimal implementation of the monotonic stack technique.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the monotonic stack approach (Approach 2 or 3) is best for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Monotonic Stack with Two Passes	O(n)	O(n)	No	Yes	Good to code if comfortable with stacks
3. Optimized Monotonic Stack Single Pass	O(n)	O(n)	No	Yes	Best approach to code for clean and efficient solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain the monotonic stack technique clearly.

How to Present

Clarify the problem and constraints.Explain the brute force approach to show understanding.Discuss inefficiency and motivate the need for optimization.Introduce monotonic stacks to find previous and next smaller elements.Explain how each element's contribution is counted using boundaries.Optionally, present the single-pass optimized monotonic stack solution.Code carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Optimize: 3min. Total ~20min

What the Interviewer Tests

Understanding of subarray enumeration, monotonic stack usage, boundary calculations, and modular arithmetic.

Common Follow-ups

• What if we want sum of subarray maximums? → Use similar approach with reversed inequalities.
• Can you handle duplicates differently? → Adjust comparison operators in stack logic.

💡 These follow-ups test flexibility with monotonic stacks and understanding of boundary conditions.

🔍

Pattern Recognition

When to Use

1) Asked for sum or count over all subarrays, 2) Minimum or maximum element involved, 3) Need to find boundaries of elements, 4) Large input size requiring O(n) or O(n log n) solution.

Signature Phrases

'sum of minimum values of every contiguous subarray''find previous smaller and next smaller elements'

NOT This Pattern When

Problems asking for maximum subarray sum or longest increasing subsequence use different techniques.

Similar Problems

Largest Rectangle in Histogram - uses monotonic stack to find boundariesSum of Subarray Maximums - similar technique with reversed inequalities

Practice

1. Given the following Python code for the Basic Calculator, what is the value of result immediately after processing the character ')' at index 6 in the input string "(1+(2-3))"?

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Add last number and combine
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
    result += sign * num
    return result

easy

A. 0

B. 0

C. 0

D. 0

Solution

1. Step 1: Trace characters up to index 6

   Input: "(1+(2-3))" - i=0:'(' push 0 and 1, result=0, sign=1 - i=1:'1' num=1 - i=2:'+' result=0+1*1=1, num=0, sign=1 - i=3:'(' push 1 and 1, result=0, sign=1 - i=4:'2' num=2 - i=5:'-' result=0+1*2=2, num=0, sign=-1 - i=6:'3' num=3

2. Step 2: Process character at index 6 (')')

   At ')': result += sign*num = 2 + (-1)*3 = -1 num=0 result *= stack.pop() -> result *= 1 -> -1 result += stack.pop() -> -1 + 1 = 0

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Result after popping stack is 0 [OK]

Hint: Remember to apply sign*num before popping stack [OK]

Common Mistakes:

• Forgetting to add last number before popping stack

2. Consider the following code for a circular queue of capacity 3. After executing these operations in order: enQueue(1), enQueue(2), enQueue(3), deQueue(), enQueue(4), what is the value of the tail pointer?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace enQueue(1), enQueue(2), enQueue(3)

   Initially, head=0, tail=0, size=0. After enQueue(1): tail=1, size=1; enQueue(2): tail=2, size=2; enQueue(3): tail=0 (wrap-around), size=3.

2. Step 2: Trace deQueue() and enQueue(4)

   deQueue() moves head from 0 to 1, size=2. enQueue(4) inserts at tail=0, then tail=1, size=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tail pointer wraps modulo capacity, final tail=1 after last enQueue [OK]

Hint: Tail pointer increments modulo capacity [OK]

Common Mistakes:

• Forgetting modulo wrap-around
• Off-by-one tail position
• Confusing head and tail pointers

3. You need to design a data structure that supports push, pop, top, and retrieving the minimum element in constant time. Which approach guarantees all operations run in O(1) time without scanning the entire stack for the minimum each time?

easy

A. Use a brute force stack and scan the entire stack to find the minimum on each getMin call.

B. Use a dynamic programming table to store minimums for all sub-stacks and update it on each push/pop.

C. Keep two stacks: one for all elements and one for minimum elements, pushing to the min stack only when a new minimum is found.

D. Maintain a single stack that stores the difference between the pushed value and the current minimum, updating the minimum accordingly.

Solution

1. Step 1: Understand the problem constraints

   The goal is to achieve O(1) time for all operations including getMin, without scanning the entire stack.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n), dynamic programming is unnecessary and inefficient, two stacks approach works but uses extra space. The single stack with encoded differences stores relative values and updates min in O(1) time and space efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single stack encoding achieves O(1) time and O(n) space with one stack [OK]

Hint: Single stack encoding stores differences for O(1) min retrieval [OK]

Common Mistakes:

• Thinking scanning stack for min is acceptable
• Confusing two-stack approach as optimal space
• Assuming DP is needed for min tracking

4. What is the time complexity of the optimal monotonic stack solution for the Largest Rectangle in Histogram problem, and why?

medium

A. O(n) because each bar is pushed and popped at most once from the stack

B. O(n) but with O(n^2) worst-case due to stack operations

C. O(n^2) because nested loops are used to find boundaries

D. O(n log n) because each element is pushed and popped multiple times

Solution

1. Step 1: Analyze stack operations

   Each bar is pushed once and popped at most once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops over all elements

   Loops run linearly, no repeated scanning of all elements inside inner loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time complexity due to amortized stack operations [OK]

Hint: Each element pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming stack operations cause O(n log n) or O(n^2)
• Confusing nested loops in brute force with stack approach

5. The following code attempts to implement the Remove K Digits algorithm. Which line contains a subtle bug that can cause incorrect results on inputs with leading zeros?

medium

A. Line joining builder into result without stripping leading zeros

B. Line where digits are appended to builder

C. Line with while loop popping digits

D. Line slicing builder when k > 0

Solution

1. Step 1: Identify handling of leading zeros

   The code joins builder into a string but does not remove leading zeros, which can cause incorrect minimal number representation.

2. Step 2: Pinpoint the bug line

   The line joining builder lacks lstrip('0'), so leading zeros remain, violating problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Leading zeros must be stripped to get correct minimal number [OK]

Hint: Always strip leading zeros after building number [OK]

Common Mistakes:

• Forgetting to strip leading zeros
• Removing digits incorrectly when k > 0