Basic Calculator (With Parentheses)

🎯

Basic Calculator (With Parentheses)

hardSTACKGoogleAmazonFacebook

Imagine building a simple calculator app that can handle addition, subtraction, and nested parentheses, just like a real calculator on your phone.

💡 This problem is about parsing and evaluating arithmetic expressions with nested parentheses. Beginners often struggle because they try to evaluate expressions left-to-right without respecting operator precedence or parentheses, leading to incorrect results.

📋

Problem Statement

Given a string s representing a valid arithmetic expression containing digits, '+', '-', '(', ')', and spaces, implement a basic calculator to evaluate it and return the result as an integer. The expression is guaranteed to be valid and may contain nested parentheses.

1 ≤ s.length ≤ 10^5s consists of digits, '+', '-', '(', ')', and ' ' (space) characters.The expression is always valid.No multiplication or division operators are present.

💡

Example

Input"\"1 + 1\""

Output2

Simple addition without parentheses.

Input"\" 2-1 + 2 \""

Output3

Addition and subtraction with spaces.

Input"\"(1+(4+5+2)-3)+(6+8)\""

Output23

Nested parentheses evaluated correctly.

• "" (empty string) → 0
• "(1)" → 1
• "- (3 + (4 + 5))" → -12
• "2147483647" → 2147483647 (max int value)

⚠️

Common Mistakes

Not handling multi-digit numbers correctly

Calculates only single digits, leading to wrong results

✅ Accumulate digits into a number before applying operators

Ignoring spaces in the input

Code may crash or misinterpret spaces as operators

✅ Skip spaces or ignore them during parsing

Not applying the last accumulated number after loop ends

Final number is lost, resulting in incorrect total

✅ Add the last number to result after the loop

Incorrectly handling sign changes after parentheses

Signs inside parentheses are not applied correctly, causing wrong results

✅ Use stack to save and restore signs when entering and exiting parentheses

Stack underflow when popping without checking

Runtime error or crash

✅ Ensure stack is not empty before popping, or rely on problem constraints

🧠

Brute Force (Recursive Parsing with String Manipulation)

💡 This approach exists to build intuition by directly parsing and evaluating the expression recursively without any optimization. It helps understand the problem structure before improving efficiency.

Intuition

Recursively evaluate the expression by scanning characters. When encountering '(', recursively evaluate the sub-expression inside. Use a helper function to parse numbers and operators step-by-step.

Algorithm

1. Define a recursive helper function that takes the expression string and current index.
2. Iterate through the string, building numbers and applying '+' or '-' operators.
3. When '(' is encountered, recursively evaluate the sub-expression until the matching ')'.
4. Return the computed sum and the current index to the caller.

💡 The recursion and index passing can be tricky to track, but it mirrors how nested parentheses naturally group expressions.

</>

Code

def calculate(s: str) -> int:
    def helper(i: int) -> (int, int):
        total = 0
        sign = 1
        num = 0
        while i < len(s):
            c = s[i]
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '+':
                total += sign * num
                num = 0
                sign = 1
            elif c == '-':
                total += sign * num
                num = 0
                sign = -1
            elif c == '(':
                num, i = helper(i + 1)
            elif c == ')':
                total += sign * num
                return total, i
            i += 1
        total += sign * num
        return total, i
    result, _ = helper(0)
    return result

# Driver code
if __name__ == '__main__':
    print(calculate("(1+(4+5+2)-3)+(6+8)"))  # Output: 23

Line Notes

def helper(i: int) -> (int, int):Defines a recursive helper that returns the computed sum and current index to handle nested parentheses.

if c.isdigit():Builds the current number digit by digit to handle multi-digit numbers.

elif c == '(':Recursively evaluates the expression inside parentheses.

elif c == ')':Returns the current total and index when closing a parenthesis is found.

import java.util.*;
public class BasicCalculator {
    public int calculate(String s) {
        return helper(s, 0)[0];
    }
    private int[] helper(String s, int i) {
        int total = 0, sign = 1, num = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                total += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                total += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                int[] res = helper(s, i + 1);
                num = res[0];
                i = res[1];
            } else if (c == ')') {
                total += sign * num;
                return new int[]{total, i};
            }
            i++;
        }
        total += sign * num;
        return new int[]{total, i};
    }
    public static void main(String[] args) {
        BasicCalculator calc = new BasicCalculator();
        System.out.println(calc.calculate("(1+(4+5+2)-3)+(6+8)")); // 23
    }
}

Line Notes

private int[] helper(String s, int i) {Helper returns an int array with result and current index to handle recursion.

if (Character.isDigit(c)) {Accumulates multi-digit numbers from characters.

int[] res = helper(s, i + 1);Recursively evaluates expression inside parentheses.

return new int[]{total, i};Returns partial result and index when closing parenthesis is found.

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

class Solution {
public:
    pair<int,int> helper(const string& s, int i) {
        int total = 0, sign = 1, num = 0;
        while (i < (int)s.size()) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                total += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                total += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                auto res = helper(s, i + 1);
                num = res.first;
                i = res.second;
            } else if (c == ')') {
                total += sign * num;
                return {total, i};
            }
            i++;
        }
        total += sign * num;
        return {total, i};
    }
    int calculate(string s) {
        return helper(s, 0).first;
    }
};

int main() {
    Solution sol;
    cout << sol.calculate("(1+(4+5+2)-3)+(6+8)") << endl; // 23
    return 0;
}

Line Notes

pair<int,int> helper(const string& s, int i) {Returns a pair with the computed sum and current index for recursion.

if (isdigit(c)) {Builds multi-digit numbers from consecutive digits.

auto res = helper(s, i + 1);Recursively evaluates sub-expression inside parentheses.

return {total, i};Returns result and index when closing parenthesis is encountered.

var calculate = function(s) {
    function helper(i) {
        let total = 0, sign = 1, num = 0;
        while (i < s.length) {
            let c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c.charCodeAt(0) - '0'.charCodeAt(0));
            } else if (c === '+') {
                total += sign * num;
                num = 0;
                sign = 1;
            } else if (c === '-') {
                total += sign * num;
                num = 0;
                sign = -1;
            } else if (c === '(') {
                let res = helper(i + 1);
                num = res[0];
                i = res[1];
            } else if (c === ')') {
                total += sign * num;
                return [total, i];
            }
            i++;
        }
        total += sign * num;
        return [total, i];
    }
    return helper(0)[0];
};

// Test
console.log(calculate("(1+(4+5+2)-3)+(6+8)")); // 23

Line Notes

function helper(i) {Helper function returns [result, index] to handle nested parentheses recursively.

if (c >= '0' && c <= '9') {Accumulates multi-digit numbers from characters.

let res = helper(i + 1);Recursively evaluates expression inside parentheses.

return [total, i];Returns partial result and index when closing parenthesis is found.

⏱

Complexity

TimeO(n)

SpaceO(n)

The recursive helper function processes each character once, using an index to avoid substring slicing. The recursion depth depends on parentheses nesting, leading to O(n) space for the call stack.

💡 Although recursion is used, each character is visited once, so the time is linear. The call stack grows with nested parentheses.

Interview Verdict: TLE on large inputs

This approach is too slow for large inputs but is valuable to understand the problem structure before optimizing.

🧠

Stack-Based Iterative Evaluation

💡 This approach uses a stack to simulate recursion and handle nested parentheses iteratively, which is more efficient and easier to implement in interviews.

Intuition

Use a stack to store intermediate results and signs when encountering '('. When ')' is found, pop and combine results. This avoids recursion overhead.

Algorithm

1. Initialize a stack, result = 0, sign = 1, and num = 0.
2. Iterate through each character in the string.
3. Build numbers from digits; on '+' or '-', add previous number with sign to result and update sign.
4. On '(', push current result and sign to stack, reset them for new sub-expression.
5. On ')', add last number to result, then multiply by sign popped from stack and add to previous result popped from stack.

💡 The stack keeps track of previous context before parentheses, allowing correct evaluation order without recursion.

</>

Code

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '+':
            result += sign * num
            num = 0
            sign = 1
        elif c == '-':
            result += sign * num
            num = 0
            sign = -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Complete current sub-expression
            result += sign * num
            num = 0
            result *= stack.pop()  # sign
            result += stack.pop()  # previous result
    result += sign * num
    return result

# Driver code
if __name__ == '__main__':
    print(calculate("(1+(4+5+2)-3)+(6+8)"))  # Output: 23

Line Notes

stack = []Stack stores previous results and signs before parentheses.

if c.isdigit():Builds multi-digit numbers from digits.

stack.append(result)Push current result before entering parentheses.

result *= stack.pop()Apply sign from stack to current sub-expression result.

import java.util.*;
public class BasicCalculator {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int result = 0, sign = 1, num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.pop();
                result += stack.pop();
            }
        }
        result += sign * num;
        return result;
    }
    public static void main(String[] args) {
        BasicCalculator calc = new BasicCalculator();
        System.out.println(calc.calculate("(1+(4+5+2)-3)+(6+8)")); // 23
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Stack holds previous results and signs before parentheses.

if (Character.isDigit(c)) {Accumulates multi-digit numbers.

stack.push(result);Save current result before processing parentheses.

result *= stack.pop();Apply sign from stack to current sub-expression result.

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

class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        int result = 0, sign = 1, num = 0;
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stk.push(result);
                stk.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stk.top(); stk.pop();
                result += stk.top(); stk.pop();
            }
        }
        result += sign * num;
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.calculate("(1+(4+5+2)-3)+(6+8)") << endl; // 23
    return 0;
}

Line Notes

stack<int> stk;Stack stores previous results and signs before parentheses.

if (isdigit(c)) {Builds multi-digit numbers.

stk.push(result);Save current result before entering parentheses.

result *= stk.top(); stk.pop();Apply sign from stack to current sub-expression result.

var calculate = function(s) {
    let stack = [];
    let result = 0, sign = 1, num = 0;
    for (let c of s) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c.charCodeAt(0) - '0'.charCodeAt(0));
        } else if (c === '+') {
            result += sign * num;
            num = 0;
            sign = 1;
        } else if (c === '-') {
            result += sign * num;
            num = 0;
            sign = -1;
        } else if (c === '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c === ')') {
            result += sign * num;
            num = 0;
            result *= stack.pop();
            result += stack.pop();
        }
    }
    result += sign * num;
    return result;
};

// Test
console.log(calculate("(1+(4+5+2)-3)+(6+8)")); // 23

Line Notes

let stack = [];Stack keeps track of previous results and signs before parentheses.

if (c >= '0' && c <= '9') {Accumulates multi-digit numbers.

stack.push(result);Save current result before processing parentheses.

result *= stack.pop();Apply sign from stack to current sub-expression result.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each character is processed once, and the stack stores at most O(n) elements for nested parentheses.

💡 For n=20, about 20 operations, which is efficient and scalable.

Interview Verdict: Accepted

This is the standard efficient approach to solve the problem in interviews.

🧠

Optimized Stack with Immediate Number Processing

💡 This approach refines the stack method by processing numbers immediately when operators or parentheses are encountered, reducing temporary variables and improving clarity.

Intuition

Instead of waiting to add numbers to result, add them immediately when an operator or parenthesis is found. This reduces complexity and makes the code cleaner.

Algorithm

1. Initialize stack, result = 0, sign = 1, and num = 0.
2. Iterate through characters, building numbers.
3. When encountering '+', '-', '(', or ')', add the current number to result with sign, then update sign or stack accordingly.
4. On '(', push current result and sign, reset them.
5. On ')', add last number, then pop sign and previous result from stack and combine.

💡 Immediate processing of numbers simplifies state management and reduces bugs related to delayed addition.

</>

Code

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

# Driver code
if __name__ == '__main__':
    print(calculate("(1+(4+5+2)-3)+(6+8)"))  # Output: 23

Line Notes

for i, c in enumerate(s):Enumerate to process each character with index, useful for debugging or extensions.

elif c in '+-':Immediately add the accumulated number to result before updating sign.

stack.append(result)Push current result before entering parentheses.

result *= stack.pop()Apply sign from stack to current sub-expression result.

import java.util.*;
public class BasicCalculator {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int result = 0, sign = 1, num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.pop();
                result += stack.pop();
            }
        }
        result += sign * num;
        return result;
    }
    public static void main(String[] args) {
        BasicCalculator calc = new BasicCalculator();
        System.out.println(calc.calculate("(1+(4+5+2)-3)+(6+8)")); // 23
    }
}

Line Notes

for (int i = 0; i < s.length(); i++) {Iterate over each character by index for clarity and possible extensions.

else if (c == '+' || c == '-') {Add current number to result before updating sign immediately.

stack.push(result);Save current result before processing parentheses.

result *= stack.pop();Apply sign from stack to current sub-expression result.

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

class Solution {
public:
    int calculate(string s) {
        stack<int> stk;
        int result = 0, sign = 1, num = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                stk.push(result);
                stk.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stk.top(); stk.pop();
                result += stk.top(); stk.pop();
            }
        }
        result += sign * num;
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.calculate("(1+(4+5+2)-3)+(6+8)") << endl; // 23
    return 0;
}

Line Notes

for (int i = 0; i < (int)s.size(); i++) {Index-based iteration for clarity and possible debugging.

else if (c == '+' || c == '-') {Add current number to result before updating sign immediately.

stk.push(result);Save current result before entering parentheses.

result *= stk.top(); stk.pop();Apply sign from stack to current sub-expression result.

var calculate = function(s) {
    let stack = [];
    let result = 0, sign = 1, num = 0;
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c.charCodeAt(0) - '0'.charCodeAt(0));
        } else if (c === '+' || c === '-') {
            result += sign * num;
            num = 0;
            sign = (c === '+') ? 1 : -1;
        } else if (c === '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c === ')') {
            result += sign * num;
            num = 0;
            result *= stack.pop();
            result += stack.pop();
        }
    }
    result += sign * num;
    return result;
};

// Test
console.log(calculate("(1+(4+5+2)-3)+(6+8)")); // 23

Line Notes

for (let i = 0; i < s.length; i++) {Index-based iteration for clarity and debugging.

else if (c === '+' || c === '-') {Add current number to result before updating sign immediately.

stack.push(result);Save current result before processing parentheses.

result *= stack.pop();Apply sign from stack to current sub-expression result.

⏱

Complexity

TimeO(n)

SpaceO(n)

Processes each character once; stack size depends on parentheses nesting depth.

💡 For n=20, about 20 operations, efficient and clean.

Interview Verdict: Accepted

This is a clean, maintainable approach suitable for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the stack-based iterative approach (Approach 2 or 3) is preferred for clarity and efficiency. Brute force recursion is useful to explain but not practical to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Parsing)	O(n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Stack-Based Iterative Evaluation	O(n)	O(n) stack for parentheses	No	N/A	Code this approach
3. Optimized Stack with Immediate Number Processing	O(n)	O(n)	No	N/A	Code this approach for cleaner code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to stack-based solutions for efficiency. Practice coding and testing edge cases.

How to Present

Step 1: Clarify input format and allowed characters.Step 2: Describe brute force recursive parsing to handle parentheses.Step 3: Explain iterative stack-based approach to improve efficiency.Step 4: Code the stack-based solution carefully, explaining each step.Step 5: Test with examples and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

Interviewer tests your understanding of expression parsing, handling nested parentheses, stack usage, and code correctness under edge cases.

Common Follow-ups

• How to extend to handle multiplication and division? → Use operator precedence and two stacks or shunting yard algorithm.
• How to handle invalid expressions? → Add validation checks and error handling.

💡 Follow-ups test your ability to extend the solution and handle real-world input robustness.

🔍

Pattern Recognition

When to Use

1) Expression contains nested parentheses; 2) Only addition and subtraction operators; 3) Need to respect operator precedence via parentheses; 4) Input is a string with spaces.

Signature Phrases

'(', ')''+', '-''valid arithmetic expression'

NOT This Pattern When

Problems involving only single-level expressions without parentheses or those requiring full parsing with multiplication/division precedence.

Similar Problems

Basic Calculator II - extends to multiplication and division with precedenceEvaluate Reverse Polish Notation - postfix expression evaluationExpression Add Operators - advanced expression parsing with operator insertion

Practice

1. You need to evaluate a string expression containing non-negative integers and the operators +, -, *, and /, without any parentheses. The expression must respect operator precedence (multiplication and division before addition and subtraction). Which approach guarantees correct evaluation of such expressions?

easy

A. Use a stack to immediately evaluate multiplication and division, then sum the results for addition and subtraction.

B. Evaluate the expression strictly from left to right, ignoring operator precedence.

C. Use dynamic programming to store intermediate results for all subexpressions.

D. Sort the operators by precedence and evaluate all operators of the same precedence level in separate passes.

Solution

1. Step 1: Understand operator precedence

   Multiplication and division must be evaluated before addition and subtraction to get the correct result.

2. Step 2: Recognize stack-based immediate evaluation

   Using a stack to immediately compute * and / while postponing + and - ensures correct precedence without complex parsing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack-based immediate evaluation is the classic pattern for this problem [OK]

Hint: Stack handles precedence by immediate * and / evaluation [OK]

Common Mistakes:

• Ignoring operator precedence
• Trying to evaluate left to right
• Using DP unnecessarily

2. Given the following code for sliding window maximum, what is the returned list when nums = [2, 1, 3] and k = 2?

easy

A. [3, 3]

B. [2, 1]

C. [1, 3]

D. [2, 3]

Solution

1. Step 1: Trace iteration i=0

   dq empty, append index 0 (value 2). No output yet since i < k-1.

2. Step 2: Trace iteration i=1

   nums[1]=1 < nums[0]=2, so append index 1. Window size reached, max is nums[dq[0]]=2.

3. Step 3: Trace iteration i=2

   nums[2]=3 > nums[1]=1 pop index 1, nums[2]=3 > nums[0]=2 pop index 0, append index 2. Max is nums[2]=3.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Output matches expected sliding window max [OK]

Hint: Pop smaller elements before appending new index [OK]

Common Mistakes:

• Forgetting to remove out-of-window indices
• Appending max too early or late

3. The following code attempts to compute the largest rectangle area in a histogram using a monotonic stack. Identify the line containing the subtle bug that causes incorrect area calculation in some cases.

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n
    right = [n] * n
    stack = []

    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    stack.clear()

    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    max_area = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)
    return max_area

medium

A. Line with 'while stack and heights[stack[-1]] >= heights[i]:' in right boundary computation

B. Line with 'stack.clear()' before computing right boundaries

C. Line with 'width = right[i] - left[i] - 1' in area calculation

D. Line with 'while stack and heights[stack[-1]] > heights[i]:' in left boundary computation

Solution

1. Step 1: Compare left boundary condition with right boundary

   Left boundary uses '>=' but right boundary also uses '>='; originally left boundary used '>' causing inconsistency.

2. Step 2: Identify impact of using '>' instead of '>='

   Using '>' misses popping bars equal in height, leading to wrong left boundaries and smaller area.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing '>' to '>=' in left boundary fixes the bug [OK]

Hint: Use consistent '>=' in both boundary computations [OK]

Common Mistakes:

• Mixing '>' and '>=' causing inconsistent boundaries
• Forgetting to clear stack before right boundary pass

4. Consider the following buggy code for validating parentheses. Which line contains the subtle bug that can cause a runtime error or incorrect result?

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

medium

A. Line checking if stack[-1] != pairs[char]

B. Line popping from stack: stack.pop()

C. Line appending opening bracket: stack.append(char)

D. Line iterating over characters: for char in s

Solution

1. Step 1: Identify potential runtime errors

   Accessing stack[-1] without checking if stack is empty can cause IndexError if stack is empty.

2. Step 2: Check code logic

   Before comparing stack[-1], code must verify stack is not empty. Missing this check causes runtime error or incorrect acceptance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing empty stack check before stack[-1] access [OK]

Hint: Always check stack emptiness before accessing top [OK]

Common Mistakes:

• Forgetting to check if stack is empty before popping or peeking

5. Suppose you want to extend the Minimum Stack to support a new operation getMinK(k) that returns the k-th smallest element in the stack in O(1) time. Which modification to the single stack with encoded minimums approach is most appropriate?

hard

A. Maintain a balanced binary search tree alongside the stack to track all elements for quick k-th minimum queries.

B. Modify the encoding to store differences for all k smallest elements in the single stack.

C. Use multiple auxiliary stacks, each tracking the minimum for a different k value.

D. Store all elements in a sorted array and update it on every push and pop to answer getMinK in O(1).

Solution

1. Step 1: Understand getMinK(k) requirement

   Retrieving the k-th smallest element in O(1) requires a data structure supporting order statistics efficiently.

2. Step 2: Evaluate options

   Encoding differences only tracks minimum, not order statistics. Multiple stacks or sorted arrays are inefficient for updates. Balanced BST or order-statistics tree supports O(log n) updates and O(1) k-th minimum retrieval with augmentation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with order statistics is standard for k-th minimum queries [OK]

Hint: Order statistics require balanced tree, not simple stack encoding [OK]

Common Mistakes:

• Trying to encode multiple mins in one stack
• Using multiple stacks without order info
• Sorting array on every update is inefficient