Basic Calculator II (No Parentheses)

🎯

Basic Calculator II (No Parentheses)

mediumSTACKAmazonFacebookGoogle

Imagine building a simple calculator app that can evaluate expressions with addition, subtraction, multiplication, and division, but without parentheses. How do you correctly compute the result respecting operator precedence?

💡 This problem is about parsing and evaluating arithmetic expressions without parentheses. Beginners often struggle because they must handle operator precedence and associativity correctly, which is not trivial without using built-in evaluation functions.

📋

Problem Statement

Given a string s which represents a valid arithmetic expression containing non-negative integers, '+', '-', '*', and '/' operators, evaluate the expression and return the integer result. The integer division should truncate toward zero. The expression does not contain any parentheses and is guaranteed to be valid.

1 ≤ s.length ≤ 10^5s consists of digits, '+', '-', '*', '/', and spaces ' ' only.The integer division should truncate toward zero.The expression is always valid.

💡

Example

Input"\"3+2*2\""

Output7

Multiplication has higher precedence, so 2*2=4, then 3+4=7.

Input"\" 3/2 \""

Output1

3 divided by 2 truncates toward zero, so result is 1.

Input"\" 3+5 / 2 \""

Output5

5/2=2 truncates, then 3+2=5.

• Expression with only one number → returns that number
• Expression with spaces between every character → correct parsing
• Division by 1 → returns the original number
• Expression ending with a number → correctly processes last number

⚠️

Common Mistakes

Ignoring operator precedence and evaluating left to right

Incorrect results for expressions with multiplication/division

✅ Use a stack or track last number to handle precedence

Not handling spaces correctly

Parsing errors or incorrect numbers

✅ Remove spaces before parsing or skip spaces during parsing

Incorrect integer division truncation for negative numbers

Wrong results when dividing negative numbers

✅ Use truncation toward zero logic, e.g., -(-a // b) for negatives

Not processing the last number after loop ends

Last number ignored, wrong final result

✅ Ensure to process last number when end of string is reached

Using float division instead of integer division

Results with decimals instead of truncated integers

✅ Use integer division operators and truncation logic

🧠

Brute Force (Evaluate Left to Right Ignoring Precedence)

💡 This approach helps understand why operator precedence matters by showing what happens if you just evaluate from left to right without considering precedence.

Intuition

Evaluate the expression strictly from left to right, performing operations as they appear, ignoring operator precedence.

Algorithm

1. Parse the expression from left to right.
2. Extract numbers and operators in order.
3. Apply each operator immediately to the current result and next number, strictly left to right.
4. Return the final result after processing all operators.

💡 This algorithm is straightforward but fails for multiplication and division precedence, which is why it is a good starting point.

</>

Code

def calculate(s: str) -> int:
    s = s.replace(' ', '')
    total = 0
    current_num = 0
    current_op = '+'
    i = 0
    while i < len(s):
        if s[i].isdigit():
            current_num = current_num * 10 + int(s[i])
        if i == len(s) - 1 or s[i] in '+-*/':
            if current_op == '+':
                total += current_num
            elif current_op == '-':
                total -= current_num
            elif current_op == '*':
                total = total * current_num
            elif current_op == '/':
                # Use int() to truncate toward zero
                total = int(total / current_num)
            current_op = s[i]
            current_num = 0
        i += 1
    return total

# Driver code
if __name__ == '__main__':
    print(calculate("3+2*2"))  # Output: 7

Line Notes

s = s.replace(' ', '')Remove spaces to simplify parsing.

total = 0Initialize total to accumulate result.

current_num = 0Holds the current number being parsed.

if s[i].isdigit()Build multi-digit numbers by accumulating digits.

if i == len(s) - 1 or s[i] in '+-*/'When operator or end reached, apply previous operator.

if current_op == '+':Apply addition to total.

elif current_op == '*':Multiply total by current number (incorrect precedence but per brute force).

current_op = s[i]Update operator for next operation.

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        int total = 0;
        int currentNum = 0;
        char currentOp = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
            }
            if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
                if (currentOp == '+') total += currentNum;
                else if (currentOp == '-') total -= currentNum;
                else if (currentOp == '*') total = total * currentNum;
                else if (currentOp == '/') total = total / currentNum;
                currentOp = c;
                currentNum = 0;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.calculate("3+2*2")); // Output: 7
    }
}

Line Notes

s = s.replace(" ", "")Remove spaces to simplify parsing.

int total = 0;Initialize total to accumulate result.

int currentNum = 0;Holds the current number being parsed.

if (Character.isDigit(c))Build multi-digit numbers by accumulating digits.

if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/')When operator or end reached, apply previous operator.

if (currentOp == '+') total += currentNum;Apply addition to total.

else if (currentOp == '*') total = total * currentNum;Multiply total by current number (incorrect precedence but per brute force).

currentOp = c;Update operator for next operation.

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

int calculate(string s) {
    s.erase(remove(s.begin(), s.end(), ' '), s.end());
    int total = 0;
    int currentNum = 0;
    char currentOp = '+';
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            currentNum = currentNum * 10 + (c - '0');
        }
        if (i == s.size() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
            if (currentOp == '+') total += currentNum;
            else if (currentOp == '-') total -= currentNum;
            else if (currentOp == '*') total = total * currentNum;
            else if (currentOp == '/') total = total / currentNum;
            currentOp = c;
            currentNum = 0;
        }
    }
    return total;
}

int main() {
    cout << calculate("3+2*2") << endl; // Output: 7
    return 0;
}

Line Notes

s.erase(remove(s.begin(), s.end(), ' '), s.end());Remove spaces to simplify parsing.

int total = 0;Initialize total to accumulate result.

int currentNum = 0;Holds the current number being parsed.

if (isdigit(c))Build multi-digit numbers by accumulating digits.

if (i == s.size() - 1 || c == '+' || c == '-' || c == '*' || c == '/')When operator or end reached, apply previous operator.

if (currentOp == '+') total += currentNum;Apply addition to total.

else if (currentOp == '*') total = total * currentNum;Multiply total by current number (incorrect precedence but per brute force).

currentOp = c;Update operator for next operation.

function calculate(s) {
    s = s.replace(/ /g, '');
    let total = 0;
    let currentNum = 0;
    let currentOp = '+';
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (!isNaN(c)) {
            currentNum = currentNum * 10 + Number(c);
        }
        if (i === s.length - 1 || ['+', '-', '*', '/'].includes(c)) {
            if (currentOp === '+') total += currentNum;
            else if (currentOp === '-') total -= currentNum;
            else if (currentOp === '*') total = total * currentNum;
            else if (currentOp === '/') total = Math.trunc(total / currentNum);
            currentOp = c;
            currentNum = 0;
        }
    }
    return total;
}

// Driver code
console.log(calculate("3+2*2")); // Output: 7

Line Notes

s = s.replace(/ /g, '');Remove spaces to simplify parsing.

let total = 0;Initialize total to accumulate result.

let currentNum = 0;Holds the current number being parsed.

if (!isNaN(c))Build multi-digit numbers by accumulating digits.

if (i === s.length - 1 || ['+', '-', '*', '/'].includes(c))When operator or end reached, apply previous operator.

if (currentOp === '+') total += currentNum;Apply addition to total.

else if (currentOp === '*') total = total * currentNum;Multiply total by current number (incorrect precedence but per brute force).

currentOp = c;Update operator for next operation.

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the string once, parsing numbers and operators, so linear time. Space is constant as we only store a few variables.

💡 For n=100,000 characters, this means about 100,000 operations, which is efficient, but the logic is incorrect for operator precedence.

Interview Verdict: Incorrect result for expressions with multiplication/division precedence

This approach is useful to show why operator precedence matters, but it produces wrong answers for many inputs, so it is not acceptable for interviews.

🧠

Stack-Based Evaluation with Immediate Multiplication/Division

💡 This approach uses a stack to defer addition and subtraction but immediately evaluates multiplication and division, correctly handling operator precedence.

Intuition

Use a stack to store numbers. For '+' and '-', push the number (or its negation). For '*' and '/', pop the last number, apply the operation, and push the result back. Sum the stack at the end.

Algorithm

1. Initialize an empty stack and variables for current number and operator.
2. Parse the expression character by character.
3. When a number is complete, depending on the previous operator, push or compute with the stack.
4. At the end, sum all numbers in the stack to get the result.

💡 This algorithm cleverly uses the stack to separate high precedence operations from low precedence ones, making the evaluation correct and efficient.

</>

Code

def calculate(s: str) -> int:
    stack = []
    current_num = 0
    current_op = '+'
    s = s.replace(' ', '')
    for i, c in enumerate(s):
        if c.isdigit():
            current_num = current_num * 10 + int(c)
        if c in '+-*/' or i == len(s) - 1:
            if current_op == '+':
                stack.append(current_num)
            elif current_op == '-':
                stack.append(-current_num)
            elif current_op == '*':
                stack.append(stack.pop() * current_num)
            elif current_op == '/':
                top = stack.pop()
                if top < 0:
                    stack.append(-(-top // current_num))
                else:
                    stack.append(top // current_num)
            current_op = c
            current_num = 0
    return sum(stack)

# Driver code
if __name__ == '__main__':
    print(calculate("3+2*2"))  # Output: 7

Line Notes

stack = []Stack stores numbers for deferred addition/subtraction.

current_num = 0Accumulates digits into a number.

if c.isdigit()Build multi-digit numbers.

if c in '+-*/' or i == len(s) - 1When operator or end reached, process previous operator.

if current_op == '+': stack.append(current_num)Add number to stack for addition.

elif current_op == '*': stack.append(stack.pop() * current_num)Multiply immediately with last number on stack.

if top < 0: stack.append(-(-top // current_num))Handle integer division truncation toward zero for negatives.

return sum(stack)Sum all deferred additions/subtractions for final result.

import java.util.*;

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int currentNum = 0;
        char currentOp = '+';
        s = s.replace(" ", "");
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
            }
            if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
                if (currentOp == '+') stack.push(currentNum);
                else if (currentOp == '-') stack.push(-currentNum);
                else if (currentOp == '*') stack.push(stack.pop() * currentNum);
                else if (currentOp == '/') {
                    int top = stack.pop();
                    if (top < 0) stack.push(-(-top / currentNum));
                    else stack.push(top / currentNum);
                }
                currentOp = c;
                currentNum = 0;
            }
        }
        int result = 0;
        while (!stack.isEmpty()) result += stack.pop();
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.calculate("3+2*2")); // Output: 7
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Stack stores numbers for deferred addition/subtraction.

int currentNum = 0;Accumulates digits into a number.

if (Character.isDigit(c))Build multi-digit numbers.

if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/')When operator or end reached, process previous operator.

if (currentOp == '+') stack.push(currentNum);Add number to stack for addition.

else if (currentOp == '*') stack.push(stack.pop() * currentNum);Multiply immediately with last number on stack.

if (top < 0) stack.push(-(-top / currentNum));Handle integer division truncation toward zero for negatives.

while (!stack.isEmpty()) result += stack.pop();Sum all deferred additions/subtractions for final result.

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

int calculate(string s) {
    stack<int> st;
    int currentNum = 0;
    char currentOp = '+';
    s.erase(remove(s.begin(), s.end(), ' '), s.end());
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            currentNum = currentNum * 10 + (c - '0');
        }
        if (i == s.size() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
            if (currentOp == '+') st.push(currentNum);
            else if (currentOp == '-') st.push(-currentNum);
            else if (currentOp == '*') {
                int top = st.top(); st.pop();
                st.push(top * currentNum);
            } else if (currentOp == '/') {
                int top = st.top(); st.pop();
                if (top < 0) st.push(-(-top / currentNum));
                else st.push(top / currentNum);
            }
            currentOp = c;
            currentNum = 0;
        }
    }
    int result = 0;
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    return result;
}

int main() {
    cout << calculate("3+2*2") << endl; // Output: 7
    return 0;
}

Line Notes

stack<int> st;Stack stores numbers for deferred addition/subtraction.

int currentNum = 0;Accumulates digits into a number.

if (isdigit(c))Build multi-digit numbers.

if (i == s.size() - 1 || c == '+' || c == '-' || c == '*' || c == '/')When operator or end reached, process previous operator.

if (currentOp == '+') st.push(currentNum);Add number to stack for addition.

else if (currentOp == '*') { int top = st.top(); st.pop(); st.push(top * currentNum); }Multiply immediately with last number on stack.

if (top < 0) st.push(-(-top / currentNum));Handle integer division truncation toward zero for negatives.

while (!st.empty()) { result += st.top(); st.pop(); }Sum all deferred additions/subtractions for final result.

function calculate(s) {
    s = s.replace(/ /g, '');
    let stack = [];
    let currentNum = 0;
    let currentOp = '+';
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (!isNaN(c)) {
            currentNum = currentNum * 10 + Number(c);
        }
        if (i === s.length - 1 || ['+', '-', '*', '/'].includes(c)) {
            if (currentOp === '+') stack.push(currentNum);
            else if (currentOp === '-') stack.push(-currentNum);
            else if (currentOp === '*') stack.push(stack.pop() * currentNum);
            else if (currentOp === '/') {
                let top = stack.pop();
                if (top < 0) stack.push(-Math.floor(-top / currentNum));
                else stack.push(Math.floor(top / currentNum));
            }
            currentOp = c;
            currentNum = 0;
        }
    }
    return stack.reduce((a, b) => a + b, 0);
}

// Driver code
console.log(calculate("3+2*2")); // Output: 7

Line Notes

s = s.replace(/ /g, '');Remove spaces to simplify parsing.

let stack = [];Stack stores numbers for deferred addition/subtraction.

if (!isNaN(c))Build multi-digit numbers.

if (i === s.length - 1 || ['+', '-', '*', '/'].includes(c))When operator or end reached, process previous operator.

if (currentOp === '+') stack.push(currentNum);Add number to stack for addition.

else if (currentOp === '*') stack.push(stack.pop() * currentNum);Multiply immediately with last number on stack.

if (top < 0) stack.push(-Math.floor(-top / currentNum));Handle integer division truncation toward zero for negatives.

return stack.reduce((a, b) => a + b, 0);Sum all deferred additions/subtractions for final result.

⏱

Complexity

TimeO(n)

SpaceO(n)

We scan the string once and use a stack that can hold up to n/2 numbers in worst case, so linear time and space.

💡 For n=100,000, this means about 100,000 operations and up to 50,000 stack entries, which is efficient and practical.

Interview Verdict: Accepted

This approach correctly handles operator precedence and is efficient, making it a common interview solution.

🧠

Optimized Stack-Based Evaluation Without Explicit Stack

💡 This approach optimizes space by using a variable to track the last number instead of a stack, while still respecting operator precedence.

Intuition

Keep track of the last number and the running total. For '+' and '-', add the last number to total and update last number. For '*' and '/', update last number by multiplying or dividing it with current number. At the end, add last number to total.

Algorithm

1. Initialize total, last number, current number, and current operator.
2. Parse the expression character by character.
3. When a number is complete, depending on the previous operator, update total and last number accordingly.
4. At the end, add the last number to total and return the result.

💡 This algorithm reduces space usage by avoiding a stack, but requires careful tracking of last number and operator.

</>

Code

def calculate(s: str) -> int:
    s = s.replace(' ', '')
    total = 0
    last_num = 0
    current_num = 0
    current_op = '+'
    for i, c in enumerate(s):
        if c.isdigit():
            current_num = current_num * 10 + int(c)
        if c in '+-*/' or i == len(s) - 1:
            if current_op == '+':
                total += last_num
                last_num = current_num
            elif current_op == '-':
                total += last_num
                last_num = -current_num
            elif current_op == '*':
                last_num = last_num * current_num
            elif current_op == '/':
                if last_num < 0:
                    last_num = -(-last_num // current_num)
                else:
                    last_num = last_num // current_num
            current_op = c
            current_num = 0
    total += last_num
    return total

# Driver code
if __name__ == '__main__':
    print(calculate("3+2*2"))  # Output: 7

Line Notes

s = s.replace(' ', '')Remove spaces to simplify parsing.

total = 0Accumulates sum of processed numbers.

last_num = 0Stores last number to handle precedence.

if c.isdigit()Build multi-digit numbers.

if c in '+-*/' or i == len(s) - 1Process operator or end of string.

if current_op == '+': total += last_num; last_num = current_numAdd last number to total, update last number for addition.

elif current_op == '*': last_num = last_num * current_numMultiply last number immediately.

total += last_numAdd last number to total at the end.

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        int total = 0, lastNum = 0, currentNum = 0;
        char currentOp = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
            }
            if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
                if (currentOp == '+') {
                    total += lastNum;
                    lastNum = currentNum;
                } else if (currentOp == '-') {
                    total += lastNum;
                    lastNum = -currentNum;
                } else if (currentOp == '*') {
                    lastNum = lastNum * currentNum;
                } else if (currentOp == '/') {
                    if (lastNum < 0) lastNum = -(-lastNum / currentNum);
                    else lastNum = lastNum / currentNum;
                }
                currentOp = c;
                currentNum = 0;
            }
        }
        total += lastNum;
        return total;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.calculate("3+2*2")); // Output: 7
    }
}

Line Notes

s = s.replace(" ", "")Remove spaces to simplify parsing.

int total = 0, lastNum = 0, currentNum = 0;Initialize accumulators and trackers.

if (Character.isDigit(c))Build multi-digit numbers.

if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/')Process operator or end of string.

if (currentOp == '+') { total += lastNum; lastNum = currentNum; }Add last number to total, update last number for addition.

else if (currentOp == '*') { lastNum = lastNum * currentNum; }Multiply last number immediately.

if (lastNum < 0) lastNum = -(-lastNum / currentNum);Handle integer division truncation toward zero for negatives.

total += lastNum;Add last number to total at the end.

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

int calculate(string s) {
    s.erase(remove(s.begin(), s.end(), ' '), s.end());
    int total = 0, lastNum = 0, currentNum = 0;
    char currentOp = '+';
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            currentNum = currentNum * 10 + (c - '0');
        }
        if (i == s.size() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
            if (currentOp == '+') {
                total += lastNum;
                lastNum = currentNum;
            } else if (currentOp == '-') {
                total += lastNum;
                lastNum = -currentNum;
            } else if (currentOp == '*') {
                lastNum = lastNum * currentNum;
            } else if (currentOp == '/') {
                if (lastNum < 0) lastNum = -(-lastNum / currentNum);
                else lastNum = lastNum / currentNum;
            }
            currentOp = c;
            currentNum = 0;
        }
    }
    total += lastNum;
    return total;
}

int main() {
    cout << calculate("3+2*2") << endl; // Output: 7
    return 0;
}

Line Notes

s.erase(remove(s.begin(), s.end(), ' '), s.end());Remove spaces to simplify parsing.

int total = 0, lastNum = 0, currentNum = 0;Initialize accumulators and trackers.

if (isdigit(c))Build multi-digit numbers.

if (i == s.size() - 1 || c == '+' || c == '-' || c == '*' || c == '/')Process operator or end of string.

if (currentOp == '+') { total += lastNum; lastNum = currentNum; }Add last number to total, update last number for addition.

else if (currentOp == '*') { lastNum = lastNum * currentNum; }Multiply last number immediately.

if (lastNum < 0) lastNum = -(-lastNum / currentNum);Handle integer division truncation toward zero for negatives.

total += lastNum;Add last number to total at the end.

function calculate(s) {
    s = s.replace(/ /g, '');
    let total = 0, lastNum = 0, currentNum = 0;
    let currentOp = '+';
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (!isNaN(c)) {
            currentNum = currentNum * 10 + Number(c);
        }
        if (i === s.length - 1 || ['+', '-', '*', '/'].includes(c)) {
            if (currentOp === '+') {
                total += lastNum;
                lastNum = currentNum;
            } else if (currentOp === '-') {
                total += lastNum;
                lastNum = -currentNum;
            } else if (currentOp === '*') {
                lastNum = lastNum * currentNum;
            } else if (currentOp === '/') {
                if (lastNum < 0) lastNum = -Math.floor(-lastNum / currentNum);
                else lastNum = Math.floor(lastNum / currentNum);
            }
            currentOp = c;
            currentNum = 0;
        }
    }
    total += lastNum;
    return total;
}

// Driver code
console.log(calculate("3+2*2")); // Output: 7

Line Notes

s = s.replace(/ /g, '');Remove spaces to simplify parsing.

let total = 0, lastNum = 0, currentNum = 0;Initialize accumulators and trackers.

if (!isNaN(c))Build multi-digit numbers.

if (i === s.length - 1 || ['+', '-', '*', '/'].includes(c))Process operator or end of string.

if (currentOp === '+') { total += lastNum; lastNum = currentNum; }Add last number to total, update last number for addition.

else if (currentOp === '*') { lastNum = lastNum * currentNum; }Multiply last number immediately.

if (lastNum < 0) lastNum = -Math.floor(-lastNum / currentNum);Handle integer division truncation toward zero for negatives.

total += lastNum;Add last number to total at the end.

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the string once and use only a few variables, so linear time and constant space.

💡 For n=100,000, this means about 100,000 operations and minimal memory usage, making it very efficient.

Interview Verdict: Accepted

This approach is optimal in both time and space and is recommended for interviews once you understand the stack approach.

📊

All Approaches - One-Glance Tradeoffs

💡 The stack-based approach (Approach 2) is the most intuitive and commonly coded in interviews; the optimized approach (Approach 3) is best for space efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - demonstrates why precedence matters
2. Stack-Based Evaluation	O(n)	O(n)	No	Yes	Commonly coded solution, easy to explain and implement
3. Optimized Stack-Free Evaluation	O(n)	O(1)	No	Yes	Optimal solution for space, recommended if comfortable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs and edge cases clearly in interviews.

How to Present

Step 1: Clarify input format and constraints, confirm no parentheses.Step 2: Present brute force approach to show naive evaluation and its flaws.Step 3: Introduce stack-based approach to handle operator precedence.Step 4: Optimize space by tracking last number instead of stack.Step 5: Code the optimal solution and test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of operator precedence, parsing, stack usage, and ability to optimize space and handle edge cases.

Common Follow-ups

• How to extend to support parentheses? → Use recursion or stack to evaluate subexpressions.
• How to handle floating point numbers? → Modify parsing and use float division.
• How to handle invalid input? → Add validation and error handling.
• How to implement without using a stack? → Use last number tracking approach.

💡 These follow-ups test your ability to generalize, handle errors, and optimize further.

🔍

Pattern Recognition

When to Use

1) Expression evaluation without parentheses, 2) Operators with different precedence, 3) Need to parse string and compute result, 4) No built-in eval allowed

Signature Phrases

'evaluate the expression''no parentheses''integer division truncates toward zero'

NOT This Pattern When

Problems with parentheses or variables requiring parsing trees or recursion

Similar Problems

Basic Calculator I - handles parentheses with recursion or stackEvaluate Reverse Polish Notation - postfix evaluation using stackExpression Add Operators - backtracking with operator precedence

Practice

1. You are given a numeric string num and an integer k. The task is to remove exactly k digits from num to produce the smallest possible number. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Greedy algorithm using a monotonic increasing stack to remove digits that are greater than the next digit

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest lexicographically

C. Simple greedy approach removing the largest digits from left to right without considering order

D. Brute force generating all combinations of digits to remove and selecting the minimal result

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach that considers digit order.

2. Step 2: Identify the optimal approach

   Using a monotonic increasing stack allows removing digits that are larger than the next digit, ensuring the smallest possible number in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack greedily removes bigger digits before smaller ones [OK]

Common Mistakes:

• Assuming simple greedy removing largest digits left to right is optimal
• Thinking DP is needed for minimal number subsequence

2. Given an integer array, you need to find the sum of the minimum values of all possible contiguous subarrays. Which algorithmic approach guarantees an optimal O(n) time complexity solution?

easy

A. Monotonic stack to find previous less and next less elements for each array element

B. Greedy approach selecting minimum elements from left to right

C. Dynamic programming with memoization of subarray minimums

D. Brute force nested loops checking all subarrays and their minimums

Solution

1. Step 1: Understand problem constraints

   The problem requires summing minimums of all subarrays efficiently, which brute force cannot do in O(n).

2. Step 2: Identify the pattern

   Monotonic stack helps find previous less and next less elements in O(n), enabling counting subarrays where each element is minimum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack finds boundaries for minimums in O(n) [OK]

Common Mistakes:

• Assuming greedy or DP solves this in O(n)
• Confusing with maximum subarray problems

3. The following code attempts to detect the 132 pattern using the optimal approach. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 4: for num in reversed(nums):

B. Line 5: if num <= third:

C. Line 7: while stack and stack[-1] < num:

D. Line 9: stack.append(num)

Solution

1. Step 1: Analyze the condition on line 5

   The original correct condition is num < third. Using num <= third incorrectly returns True when num equals third, which violates strict inequality in 132 pattern.

2. Step 2: Confirm other lines are correct

   Iteration order, stack operations, and append are correct and necessary for the algorithm.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using <= instead of < causes false positives [OK]

Hint: Strict inequality is required for pattern detection [OK]

Common Mistakes:

• Using <= instead of <
• Confusing iteration direction
• Not popping smaller elements

4. Suppose the decoding problem is extended so that the repeat counts can be zero or negative, and substrings can be reused multiple times in different parts of the string. Which modification to the stack-based decoding algorithm correctly handles these new constraints?

hard

A. Ignore zero or negative counts and treat them as 1; reuse substrings by caching decoded results in a dictionary

B. Modify the algorithm to skip substrings with zero or negative counts and use memoization to reuse decoded substrings efficiently

C. Use recursion only, as stack-based approach cannot handle zero or negative counts or reuse

D. Preprocess the string to remove zero or negative counts and decode normally without caching

Solution

1. Step 1: Handle zero or negative counts

   Zero or negative repeats mean skipping or reversing substrings; algorithm must explicitly check counts and skip or handle accordingly.

2. Step 2: Implement substring reuse

   Memoization caches decoded substrings to avoid recomputation when reused multiple times, improving efficiency.

3. Step 3: Combine skipping invalid repeats and memoization

   Stack-based approach extended with memoization and count checks correctly handles new constraints.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization plus count validation handles reuse and zero/negative repeats [OK]

Hint: Memoize decoded substrings and skip invalid repeats [OK]

Common Mistakes:

• Ignoring zero/negative counts
• Failing to cache repeated substrings

5. Suppose the problem changes so that elements in the array can be negative integers. Which modification to the monotonic stack approach is necessary to correctly compute the sum of subarray minimums?

hard

A. Add a sentinel element with value 0 at the end to ensure stack empties correctly

B. No change needed; the existing monotonic stack approach works for negative values

C. Use a different data structure like a balanced BST to handle negative values

D. Modify the comparison to use <= instead of < to handle negative duplicates

Solution

1. Step 1: Analyze effect of negative values on monotonic stack

   The monotonic stack approach relies on relative ordering, which holds regardless of sign.

2. Step 2: Confirm no structural changes needed

   Sentinel and strict < comparison still work; negative values do not break the logic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack handles negatives without modification [OK]

Hint: Monotonic stack compares values, sign does not affect correctness [OK]

Common Mistakes:

• Assuming negative values require different data structures
• Changing comparison operators unnecessarily