Evaluate Reverse Polish Notation

🎯

Evaluate Reverse Polish Notation

mediumSTACKAmazonLinkedInBloomberg

Imagine you are building a calculator app that only accepts expressions in Reverse Polish Notation (RPN), a postfix notation used in some calculators and compilers. You need to evaluate these expressions efficiently and correctly.

💡 This problem is about evaluating mathematical expressions written in postfix form, which is different from the usual infix notation. Beginners often struggle because the order of operations is implicit and must be handled using a stack, which is a new concept for many.

📋

Problem Statement

Given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation, evaluate the expression and return the result as an integer. Valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. Division between two integers should truncate toward zero.

1 ≤ tokens.length ≤ 10^5tokens[i] is either an operator: '+', '-', '*', or '/', or an integer in string formatThe given RPN expression is always valid

💡

Example

Input["2","1","+","3","*"]

Output9

((2 + 1) * 3) = 9

Input["4","13","5","/","+"]

Output6

(4 + (13 / 5)) = 6

Input["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

Output22

Complex expression evaluated step-by-step

• Single operand only → returns the operand itself
• Division resulting in negative number → truncates toward zero
• Large number of tokens → performance must be efficient
• Expression with multiple consecutive operators → still valid and handled

⚠️

Common Mistakes

Popping operands in wrong order

Incorrect results because left and right operands are swapped

✅ Always pop right operand first, then left operand

Using float division instead of integer truncation

Results differ from expected integer division, causing wrong answers

✅ Use integer division with truncation toward zero (e.g., int(left / right))

Not handling single operand input

Code may crash or return wrong result if input has only one number

✅ Ensure code returns the single number if no operators are present

Modifying input tokens array during iteration

Unexpected behavior or runtime errors

✅ Do not modify input array; use a separate stack for evaluation

Not checking for empty stack before popping

Runtime error or crash on invalid expressions

✅ Add checks or assume input is always valid as per problem statement

🧠

Brute Force (Recursive Evaluation with Backtracking)

💡 This approach tries to evaluate the expression by recursively processing tokens from the end, simulating how the expression unfolds. It is educational to understand the problem structure but inefficient for large inputs.

Intuition

Start from the last token and recursively evaluate operands for each operator by moving backward. Each operator requires two operands, so recursively find them and apply the operator.

Algorithm

1. Define a recursive function that processes tokens from the end.
2. If the current token is a number, return it as integer.
3. If the current token is an operator, recursively evaluate the two operands before it.
4. Apply the operator to the two operands and return the result.

💡 The recursion simulates the natural evaluation order of RPN but can be hard to track because it moves backward and requires managing the current index carefully.

</>

Code

class Solution:
    def evalRPN(self, tokens):
        self.index = len(tokens) - 1
        def helper():
            token = tokens[self.index]
            self.index -= 1
            if token not in '+-*/':
                return int(token)
            right = helper()
            left = helper()
            if token == '+':
                return left + right
            elif token == '-':
                return left - right
            elif token == '*':
                return left * right
            else:
                return int(left / right)  # truncate toward zero
        return helper()

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.evalRPN(["2", "1", "+", "3", "*"]))  # Output: 9

Line Notes

self.index = len(tokens) - 1Initialize index to start from the last token for backward recursion

token = tokens[self.index]Pick the current token to process

if token not in '+-*/'Base case: if token is a number, return it as integer

right = helper()Recursively evaluate the right operand first because of postfix order

left = helper()Recursively evaluate the left operand next

return int(left / right)Perform integer division truncating toward zero as per problem statement

import java.util.*;
public class Solution {
    int index;
    public int evalRPN(String[] tokens) {
        index = tokens.length - 1;
        return helper(tokens);
    }
    private int helper(String[] tokens) {
        String token = tokens[index--];
        if (!token.equals("+") && !token.equals("-") && !token.equals("*") && !token.equals("/")) {
            return Integer.parseInt(token);
        }
        int right = helper(tokens);
        int left = helper(tokens);
        switch(token) {
            case "+": return left + right;
            case "-": return left - right;
            case "*": return left * right;
            default: return left / right; // truncates toward zero
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.evalRPN(new String[]{"2", "1", "+", "3", "*"})); // 9
    }
}

Line Notes

index = tokens.length - 1;Start from the last token for recursive evaluation

String token = tokens[index--];Fetch current token and decrement index for next call

if (!token.equals("+") && ... )Check if token is a number (base case)

int right = helper(tokens);Evaluate right operand first due to postfix order

switch(token)Apply operator to left and right operands

return left / right;Integer division truncates toward zero as required

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

class Solution {
    int index;
public:
    int evalRPN(vector<string>& tokens) {
        index = tokens.size() - 1;
        return helper(tokens);
    }
private:
    int helper(vector<string>& tokens) {
        string token = tokens[index--];
        if (token != "+" && token != "-" && token != "*" && token != "/") {
            return stoi(token);
        }
        int right = helper(tokens);
        int left = helper(tokens);
        if (token == "+") return left + right;
        if (token == "-") return left - right;
        if (token == "*") return left * right;
        return left / right; // truncates toward zero
    }
};

int main() {
    Solution sol;
    vector<string> tokens = {"2", "1", "+", "3", "*"};
    cout << sol.evalRPN(tokens) << endl; // Output: 9
    return 0;
}

Line Notes

index = tokens.size() - 1;Initialize index to last token for backward recursion

string token = tokens[index--];Get current token and decrement index for next recursion

if (token != "+" && ... )Base case: token is a number, convert and return

int right = helper(tokens);Evaluate right operand first due to postfix order

return left / right;Integer division truncates toward zero as per problem

var evalRPN = function(tokens) {
    let index = tokens.length - 1;
    function helper() {
        let token = tokens[index--];
        if (token !== '+' && token !== '-' && token !== '*' && token !== '/') {
            return parseInt(token);
        }
        let right = helper();
        let left = helper();
        switch(token) {
            case '+': return left + right;
            case '-': return left - right;
            case '*': return left * right;
            case '/': return (left / right) | 0; // truncate toward zero
        }
    }
    return helper();
};

// Test
console.log(evalRPN(["2", "1", "+", "3", "*"])) // 9

Line Notes

let index = tokens.length - 1;Start from the last token for recursive evaluation

let token = tokens[index--];Get current token and decrement index for next call

if (token !== '+' && ... )Base case: token is a number, parse and return

let right = helper();Evaluate right operand first due to postfix order

return (left / right) | 0;Bitwise OR truncates division toward zero as required

⏱

Complexity

TimeO(n)

SpaceO(n)

Each token is processed once recursively, and recursion stack can go up to n in worst case.

💡 For n=20 tokens, this means about 20 recursive calls, which is manageable but can cause stack overflow for very large n.

Interview Verdict: Accepted but not optimal for large inputs due to recursion depth

This approach works but risks stack overflow and is less efficient than iterative stack-based solutions, so it's mainly educational.

🧠

Iterative Stack-Based Evaluation

💡 This is the standard and most intuitive approach to evaluate RPN expressions using a stack. It is efficient and easy to implement once you understand the stack concept.

Intuition

Scan tokens from left to right, push numbers onto a stack, and when an operator is found, pop two operands, apply the operator, and push the result back.

Algorithm

1. Initialize an empty stack.
2. Iterate over each token in the input array.
3. If the token is a number, push it onto the stack.
4. If the token is an operator, pop two numbers from the stack, apply the operator, and push the result back.
5. After processing all tokens, the stack's top element is the result.

💡 This approach is straightforward but requires careful handling of operand order and integer division.

</>

Code

class Solution:
    def evalRPN(self, tokens):
        stack = []
        for token in tokens:
            if token not in '+-*/':
                stack.append(int(token))
            else:
                right = stack.pop()
                left = stack.pop()
                if token == '+':
                    stack.append(left + right)
                elif token == '-':
                    stack.append(left - right)
                elif token == '*':
                    stack.append(left * right)
                else:
                    stack.append(int(left / right))  # truncate toward zero
        return stack.pop()

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.evalRPN(["2", "1", "+", "3", "*"]))  # Output: 9

Line Notes

stack = []Initialize stack to store operands

for token in tokens:Process tokens from left to right

if token not in '+-*/':If token is a number, push it onto the stack

right = stack.pop()Pop right operand for operator application

left = stack.pop()Pop left operand for operator application

stack.append(int(left / right))Perform integer division truncating toward zero

import java.util.*;
public class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if (!token.equals("+") && !token.equals("-") && !token.equals("*") && !token.equals("/")) {
                stack.push(Integer.parseInt(token));
            } else {
                int right = stack.pop();
                int left = stack.pop();
                switch(token) {
                    case "+": stack.push(left + right); break;
                    case "-": stack.push(left - right); break;
                    case "*": stack.push(left * right); break;
                    case "/": stack.push(left / right); break; // truncates toward zero
                }
            }
        }
        return stack.pop();
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.evalRPN(new String[]{"2", "1", "+", "3", "*"})); // 9
    }
}

Line Notes

Deque<Integer> stack = new ArrayDeque<>();Use stack to hold operands

for (String token : tokens)Iterate tokens left to right

if (!token.equals("+") && ... )Check if token is a number

int right = stack.pop();Pop right operand for operator

switch(token)Apply operator to operands

return stack.pop();Final result is on top of stack

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

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (string& token : tokens) {
            if (token != "+" && token != "-" && token != "*" && token != "/") {
                st.push(stoi(token));
            } else {
                int right = st.top(); st.pop();
                int left = st.top(); st.pop();
                if (token == "+") st.push(left + right);
                else if (token == "-") st.push(left - right);
                else if (token == "*") st.push(left * right);
                else st.push(left / right); // truncates toward zero
            }
        }
        return st.top();
    }
};

int main() {
    Solution sol;
    vector<string> tokens = {"2", "1", "+", "3", "*"};
    cout << sol.evalRPN(tokens) << endl; // Output: 9
    return 0;
}

Line Notes

stack<int> st;Stack to hold operands

for (string& token : tokens)Process tokens left to right

if (token != "+" && ... )Check if token is a number

int right = st.top(); st.pop();Pop right operand

int left = st.top(); st.pop();Pop left operand

st.push(left / right);Integer division truncates toward zero

var evalRPN = function(tokens) {
    const stack = [];
    for (const token of tokens) {
        if (token !== '+' && token !== '-' && token !== '*' && token !== '/') {
            stack.push(parseInt(token));
        } else {
            const right = stack.pop();
            const left = stack.pop();
            switch(token) {
                case '+': stack.push(left + right); break;
                case '-': stack.push(left - right); break;
                case '*': stack.push(left * right); break;
                case '/': stack.push((left / right) | 0); break; // truncate toward zero
            }
        }
    }
    return stack.pop();
};

// Test
console.log(evalRPN(["2", "1", "+", "3", "*"])) // 9

Line Notes

const stack = [];Initialize stack for operands

for (const token of tokens)Iterate tokens left to right

if (token !== '+' && ... )Check if token is a number

const right = stack.pop();Pop right operand

const left = stack.pop();Pop left operand

stack.push((left / right) | 0);Bitwise OR truncates division toward zero

⏱

Complexity

TimeO(n)

SpaceO(n)

Each token is processed once, and stack size is at most n/2 for valid RPN expressions.

💡 For n=20 tokens, about 20 pushes/pops happen, which is very efficient and safe for large inputs.

Interview Verdict: Accepted and optimal for typical interview constraints

This is the recommended approach to implement in interviews due to clarity and efficiency.

🧠

Optimized Iterative with Inline Operator Function

💡 This approach improves code readability and maintainability by using a map/dictionary for operators, reducing repetitive code.

Intuition

Use a dictionary to map operators to their corresponding lambda functions, then apply them dynamically during iteration.

Algorithm

1. Create a dictionary mapping operators to their functions.
2. Initialize an empty stack.
3. Iterate over tokens, pushing numbers or applying operator functions.
4. Pop two operands when operator is encountered, apply function, and push result.
5. Return the last element on the stack as the result.

💡 This approach is functionally the same as the previous stack method but improves code elegance and reduces bugs.

</>

Code

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                right = stack.pop()
                left = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.evalRPN(["2", "1", "+", "3", "*"]))  # Output: 9

Line Notes

import operatorImport standard operator functions for clarity

ops = { ... }Map operators to their corresponding functions

if token in ops:Check if token is an operator

stack.append(ops[token](left, right))Apply operator function dynamically

stack.append(int(token))Push number tokens as integers

import java.util.*;
import java.util.function.BiFunction;
public class Solution {
    public int evalRPN(String[] tokens) {
        Map<String, BiFunction<Integer, Integer, Integer>> ops = new HashMap<>();
        ops.put("+", (a, b) -> a + b);
        ops.put("-", (a, b) -> a - b);
        ops.put("*", (a, b) -> a * b);
        ops.put("/", (a, b) -> a / b);
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if (ops.containsKey(token)) {
                int right = stack.pop();
                int left = stack.pop();
                stack.push(ops.get(token).apply(left, right));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.evalRPN(new String[]{"2", "1", "+", "3", "*"})); // 9
    }
}

Line Notes

Map<String, BiFunction<Integer, Integer, Integer>> ops = new HashMap<>();Map operators to lambda functions for cleaner code

ops.put("+", (a, b) -> a + b);Define addition operator function

if (ops.containsKey(token))Check if token is an operator

stack.push(ops.get(token).apply(left, right));Apply operator function dynamically

stack.push(Integer.parseInt(token));Push number tokens as integers

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <functional>
using namespace std;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        unordered_map<string, function<int(int,int)>> ops = {
            {"+", [](int a, int b) { return a + b; }},
            {"-", [](int a, int b) { return a - b; }},
            {"*", [](int a, int b) { return a * b; }},
            {"/", [](int a, int b) { return a / b; }}
        };
        stack<int> st;
        for (auto& token : tokens) {
            if (ops.count(token)) {
                int right = st.top(); st.pop();
                int left = st.top(); st.pop();
                st.push(ops[token](left, right));
            } else {
                st.push(stoi(token));
            }
        }
        return st.top();
    }
};

int main() {
    Solution sol;
    vector<string> tokens = {"2", "1", "+", "3", "*"};
    cout << sol.evalRPN(tokens) << endl; // Output: 9
    return 0;
}

Line Notes

unordered_map<string, function<int(int,int)>> ops = { ... };Map operators to lambda functions for clarity

if (ops.count(token))Check if token is an operator

int right = st.top(); st.pop();Pop right operand

st.push(ops[token](left, right));Apply operator function dynamically

st.push(stoi(token));Push number tokens as integers

var evalRPN = function(tokens) {
    const ops = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => (a / b) | 0 // truncate toward zero
    };
    const stack = [];
    for (const token of tokens) {
        if (token in ops) {
            const right = stack.pop();
            const left = stack.pop();
            stack.push(ops[token](left, right));
        } else {
            stack.push(parseInt(token));
        }
    }
    return stack.pop();
};

// Test
console.log(evalRPN(["2", "1", "+", "3", "*"])) // 9

Line Notes

const ops = { ... };Map operators to arrow functions for cleaner code

if (token in ops)Check if token is an operator

const right = stack.pop();Pop right operand

stack.push(ops[token](left, right));Apply operator function dynamically

stack.push(parseInt(token));Push number tokens as integers

⏱

Complexity

TimeO(n)

SpaceO(n)

Same as previous stack approach but with cleaner code structure.

💡 This approach is just as efficient but easier to maintain and less error-prone.

Interview Verdict: Accepted and recommended for clean code

This approach is ideal for interviews where clean, maintainable code is valued.

📊

All Approaches - One-Glance Tradeoffs

💡 The iterative stack-based approach is the best choice for 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Evaluation)	O(n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Iterative Stack-Based Evaluation	O(n)	O(n) stack	No	N/A	Code this approach
3. Optimized Iterative with Operator Map	O(n)	O(n) stack + O(1) map	No	N/A	Code for cleaner, maintainable solution

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the brute force recursive approach to show understanding of RPN evaluation.Step 3: Present the iterative stack-based solution as the optimal approach.Step 4: Optionally mention the operator map for cleaner code.Step 5: Code the iterative stack solution carefully, test with examples, and discuss edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of stack usage, operator precedence in postfix notation, integer division behavior, and ability to write clean, bug-free code.

Common Follow-ups

• How to handle invalid tokens or malformed expressions → add validation and error handling
• What if division should round down instead of truncate → adjust division logic accordingly

💡 These follow-ups test your robustness and understanding of integer division nuances.

🔍

Pattern Recognition

When to Use

1) Expression evaluation is required, 2) Input is in postfix notation, 3) Operators and operands are mixed in a list, 4) Stack usage is suggested by problem constraints.

Signature Phrases

Reverse Polish Notationpostfix expressionevaluate expressionstack-based evaluation

NOT This Pattern When

Infix expression evaluation with parentheses and precedence is a different pattern requiring different parsing techniques.

Similar Problems

Basic Calculator II - evaluates infix expressions with operator precedenceExpression Add Operators - generates expressions with operatorsSimplify Path - uses stack to process path components

Practice

1. What is the time and space complexity of the optimal stack-less solution for evaluating a Basic Calculator II expression of length n?

medium

A. O(n) time and O(1) space because it processes the string once and uses only a few variables.

B. O(n^2) time and O(n) space due to repeated string slicing and stack usage.

C. O(n) time and O(n) space because it uses a stack to store intermediate results.

D. O(n log n) time due to sorting operators by precedence and O(1) space.

Solution

1. Step 1: Identify time complexity

   The algorithm scans the input string once, performing constant-time operations per character, so time is O(n).

2. Step 2: Identify space complexity

   Only a fixed number of variables are used (total, last_num, current_num, current_op), so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant variables confirm O(n) time and O(1) space [OK]

Hint: Single pass with fixed vars means O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming stack usage means O(n) space
• Confusing recursion stack with iteration
• Thinking sorting operators is needed

2. The following code attempts to implement the optimized next greater element algorithm. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line with 'while stack and num > stack[-1]:' condition

B. Line 'while stack:' loop assigning -1 to remaining elements

C. Line 'nums1_set.remove(smaller)' inside the if condition

D. Line missing 'next_greater_map[smaller] = num' inside the while loop

Solution

1. Step 1: Identify missing mapping assignment

   The code pops smaller elements but does not assign their next greater element in next_greater_map, causing missing or incorrect results.

2. Step 2: Confirm other lines are correct

   The while condition, set removal, and final assignment of -1 are all correct and necessary for correctness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without mapping assignment, queries for nums1 elements fail [OK]

Hint: Mapping next greater elements must happen immediately after popping [OK]

Common Mistakes:

• Forgetting to assign next greater element after popping from stack
• Incorrectly removing elements from nums1_set too early
• Misplacing the final assignment of -1 for leftover stack elements

3. The following code attempts to compute the sum of subarray minimums using a monotonic stack. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 11: count = (mid - left) * (i - mid)

B. Line 7: current = arr[i] if i < n else 0

C. Line 6: for i in range(n + 1):

D. Line 8: while stack and (i == n or current <= arr[stack[-1]]):

Solution

1. Step 1: Understand the condition in the while loop

   The condition uses <= instead of <, causing incorrect boundaries for next less element.

2. Step 2: Explain impact of using <=

   Using <= merges equal elements incorrectly, leading to wrong counts of subarrays and incorrect sum.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing <= to < fixes the bug and matches expected outputs [OK]

Hint: Use <, not <=, to find next less element correctly [OK]

Common Mistakes:

• Using >= or <= instead of strict inequalities
• Mixing previous less and next less boundaries

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 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