Home/DSA Complete from Scratch to Expert/dsa-topics

Stack

Master this topic with zero to advance depth.

Stack: The LIFO Mental Model

A Stack is a linear data structure that rigidly follows the Last-In, First-Out (LIFO) principle. It represents a constraint on how we access data: we can only interact with the top of the stack. Think of it like a stack of plates or a history of actions.

1. Core Operations & Complexity

A properly implemented stack guarantees $O(1)$ operations.

Operation	Description	Time Complexity	Space Complexity
`Push(x)`	Add element `x` to the top.	$O(1)$	$O(N)$ total
`Pop()`	Remove and return the top element.	$O(1)$	$O(1)$
`Peek()` / `Top()`	Return the top element without removing it.	$O(1)$	$O(1)$
`IsEmpty()`	Check if the stack has no elements.	$O(1)$	$O(1)$

2. When to Use a Stack?

Stacks are the perfect tool when processing data requires remembering past but unresolved information in the reverse order of their arrival.

Key Signals in Interviews:

Parsing/Matching: Strings with brackets, tags (HTML/XML), or valid substructures.
"Undo" or Backtracking: Reversing the most recent action (e.g., maze paths, DFS).
Deferring Execution: Postponing evaluation until sufficient data is available (Evaluators, RPN).
Next Greater/Smaller Elements: Finding the closest element that breaks a trend.

3. Stack vs. Recursion

There is a deep correspondence between Stacks and Recursion. Every recursive algorithm can be implemented iteratively using an explicit stack.

Implicit Stack: In recursion, the computer maintains a "Call Stack" for you. If the recursion is too deep, you get a StackOverflowError.
Explicit Stack: Using an Object or Array in heaps, you can often handle deeper levels of nesting and have more control over the state.

4. The Power of the Monotonic Stack

A Monotonic Stack is a regular stack where elements are forced to remain sorted (either strictly increasing or strictly decreasing). It's a magical pattern that turns $O(N^2)$ brute-force searches into $O(N)$ solutions.

How it works:

Maintain the monotonic property by popping elements that violate the rule before pushing the new element.

Goal: Find the Next Greater Element for [2, 1, 2, 4, 3]
Constraint: Stack must be Monotonic Decreasing (store unresolved elements)

1. Process '2': Stack [2]
2. Process '1': 1 < 2, so keep it. Stack [2, 1]
3. Process '2': 2 > 1. Violated! 
   - Pop '1'. The next greater for '1' is '2'. 
   - Push '2'. Stack [2, 2]
4. Process '4': 4 > 2. Violated! 
   - Pop '2'. Next greater is '4'.
   - Pop '2'. Next greater is '4'.
   - Push '4'. Stack [4]
5. Process '3': 3 < 4, so keep it. Stack [4, 3]

[!TIP] Monotonic Decreasing Stack: Use to find the Next Greater Element. Monotonic Increasing Stack: Use to find the Next Smaller Element (or previous smaller).

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Visual Representation

s = "{ [ ] }"

Step 1: '{' -> Push to Stack.    Stack: ['{']
Step 2: '[' -> Push to Stack.    Stack: ['{', '[']
Step 3: ']' -> Matches Top '['.  Pop. Stack: ['{']
Step 4: '}' -> Matches Top '{'.  Pop. Stack: []

Result: Valid (Stack is Empty)

Easy

Examples

Input: s = "()[]{}"
Output: true

Approach 1

Level I: Brute Force (String Replace)

Intuition

Regular expressions or string replacements can continuously remove valid adjacent pairs (), {}, [] until the string is empty or no more replacements can be made.

⏱ O(N^2) where N is the length of the string, as `replace` scans the string multiple times.💾 O(N) for string copies during replacement.

java

public class Solution {
    public boolean isValid(String s) {
        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.isEmpty();
    }
}

Approach 2

Level II: Recursive (Function Call Stack)

Intuition

Instead of an explicit stack object, we can use recursion. Each function call 'expects' a specific closing bracket. If it finds one, it returns; if it finds another opening bracket, it recurses. This demonstrates how the computer's memory uses a stack internally.

⏱ O(N)💾 O(N) due to recursion depth.

java

public class Solution {
    private int i = 0;
    public boolean isValid(String s) {
        return helper(s, '#');
    }
    
    private boolean helper(String s, char expected) {
        while (i < s.length()) {
            char c = s.charAt(i++);
            if (c == '(') { if (!helper(s, ')')) return false; }
            else if (c == '{') { if (!helper(s, '}')) return false; }
            else if (c == '[') { if (!helper(s, ']')) return false; }
            else return c == expected;
        }
        return expected == '#';
    }
}

Approach 3

Level III: Optimal (Stack Mapping)

Intuition

Iterate through the string. If we see an opening bracket, push its corresponding closing bracket onto the stack. If we see a closing bracket, check if it matches the top of the stack. This simplifies the logic by storing what we expect next.

⏱ O(N)💾 O(N)

Detailed Dry Run

Char	Action	Stack Status	Match?
'('	Push ')'	`[')']`	-
'['	Push ']'	`[')', ']']`	-
']'	Pop	`[')']`	Yes
')'	Pop	`[]`	Yes

java

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isValid("()[]{}")); // Output: true
    }
}

⚠️ Common Pitfalls & Tips

Be careful with strings that only contain opening brackets, or strings where the stack becomes empty too early.

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Visual Representation

Push: -2, 0, -3

Stack:      MinStack: 
| -3 |      | -3 |
|  0 |      | -2 |
| -2 |      | -2 |
+----+      +----+

getMin() -> -3
pop()
top()    -> 0
getMin() -> -2

Easy

Examples

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]\n[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]

Approach 1

Level I: Single Stack (Brute Force Min)

Intuition

Use a standard stack for push, pop, and top. For getMin(), iterate over the entire stack to find the minimum value. This saves space over a two-stack approach but sacrifices the constant-time operation for querying the minimum.

⏱ O(1) for push/pop/top. O(N) for getMin.💾 O(N) for the underlying stack.

java

import java.util.*;

class MinStack {
    private List<Integer> s = new ArrayList<>();
    public void push(int val) { s.add(val); }
    public void pop() { s.remove(s.size() - 1); }
    public int top() { return s.get(s.size() - 1); }
    public int getMin() {
        int mn = Integer.MAX_VALUE;
        for (int n : s) if (n < mn) mn = n;
        return mn;
    }
}

Approach 2

Level II: Single Stack (Value-Min Pairs)

Intuition

Instead of two separate stacks, we can store pairs on a single stack. Each entry on the stack will be (current_value, current_min_so_far). This is conceptually simpler and ensures the value and its corresponding minimum are always synchronized.

⏱ O(1) for all operations.💾 O(N) to store pairs.

java

import java.util.Stack;

class MinStack {
    private Stack<int[]> stack = new Stack<>();
    
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new int[]{val, val});
        } else {
            stack.push(new int[]{val, Math.min(val, stack.peek()[1])});
        }
    }
    
    public void pop() { stack.pop(); }
    public int top() { return stack.peek()[0]; }
    public int getMin() { return stack.peek()[1]; }
}

Approach 3

Level III: Optimal (Two Stacks)

Intuition

Maintain two stacks: one for all elements and another to keep track of the minimum at each state. When pushing a value, if it is less than or equal to the current minimum, push it onto the min stack as well. This ensures O(1) retrieval.

⏱ O(1) for all operations.💾 O(N)

Detailed Dry Run

Operation	Value	Stack	MinStack	Output
push	-2	`[-2]`	`[-2]`	-
push	0	`[-2, 0]`	`[-2]`	-
push	-3	`[-2, 0, -3]`	`[-2, -3]`	-
getMin	-	-	-	-3
pop	-	`[-2, 0]`	`[-2]`	-

java

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
    }
    
    public void pop() {
        if (stack.pop().equals(minStack.peek())) minStack.pop();
    }
    
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
    
    public static void main(String[] args) {
        MinStack ms = new MinStack();
        ms.push(-2); ms.push(0); ms.push(-3);
        System.out.println(ms.getMin()); // -3
        ms.pop();
        System.out.println(ms.top());    // 0
        System.out.println(ms.getMin()); // -2
    }
}

⚠️ Common Pitfalls & Tips

In Java, use .equals() instead of == for Stack comparisons as Integer objects might be outside the cache range.

Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two his stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Easy

Examples

Input: ["MyQueue", "push", "push", "peek", "pop", "empty"]\n[[], [1], [2], [], [], []]
Output: [null, null, null, 1, 1, false]

Approach 1

Level I: Two Stacks (Push O(N))

Intuition

To make a stack behave like a queue, the oldest entered elements must be kept at the top of the stack. For every newly pushed element, we can move all elements to a temporary stack, push the new element to the bottom, and move everything back.

⏱ O(N) for push operation, O(1) for pop and peek.💾 O(N) to store elements.

java

class MyQueue {
    java.util.Stack<Integer> s1 = new java.util.Stack<>();
    java.util.Stack<Integer> s2 = new java.util.Stack<>();
    public void push(int x) {
        while (!s1.isEmpty()) s2.push(s1.pop());
        s1.push(x);
        while (!s2.isEmpty()) s1.push(s2.pop());
    }
    public int pop() { return s1.pop(); }
    public int peek() { return s1.peek(); }
    public boolean empty() { return s1.isEmpty(); }
}

Approach 2

Level II: Recursive (One Stack)

Intuition

We can implement the 'pop' or 'peek' operation using a single stack and recursion. The function call stack acts as the second stack. To pop the bottom element, we pop the top, recurse to the bottom, and then push the popped element back as we return. This is less efficient than two stacks but insightful.

⏱ O(N) for pop/peek💾 O(N) recursion depth

java

import java.util.Stack;

class MyQueue {
    private Stack<Integer> s = new Stack<>();
    public void push(int x) { s.push(x); }
    public int pop() {
        int top = s.pop();
        if (s.isEmpty()) return top;
        int res = pop();
        s.push(top);
        return res;
    }
    public int peek() {
        int top = s.pop();
        if (s.isEmpty()) { s.push(top); return top; }
        int res = peek();
        s.push(top);
        return res;
    }
    public boolean empty() { return s.isEmpty(); }
}

Approach 3

Level III: Amortized O(1) with Two Stacks

Use an input stack to handle pushes and an output stack for peeks/pops. When the output stack is empty, transfer all elements from input to output. This reverses the order to FIFO.

⏱ O(1) amortized💾 O(N)

Detailed Dry Run

Operation	Value	in_stack	out_stack	Output
push	1	`[1]`	`[]`	-
push	2	`[1, 2]`	`[]`	-
peek	-	`[]`	`[2, 1]`	1
pop	-	`[]`	`[2]`	1
empty	-	`[]`	`[2]`	false

java

import java.util.Stack;

class MyQueue {
    private Stack<Integer> in = new Stack<>(), out = new Stack<>();
    public void push(int x) { in.push(x); }
    public int pop() {
        peek();
        return out.pop();
    }
    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Easy

Examples

Input: ["MyStack", "push", "push", "top", "pop", "empty"]\n[[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]

Approach 1

Level I: Two Queues (Push O(N))

Intuition

When a new element arrives, enqueue it to a secondary empty queue. Then, dequeue all elements from the main queue and enqueue them after the new element. Finally, swap the main and secondary queues. The newest element is now at the front.

⏱ O(N) for push operation, O(1) for pop and top.💾 O(N) to store elements.

java

import java.util.*;

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    public void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) q2.add(q1.remove());
        Queue<Integer> temp = q1; q1 = q2; q2 = temp;
    }
    public int pop() { return q1.remove(); }
    public int top() { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}

Approach 2

Level III: One Queue (Optimize Space)

When pushing an element, add it to the queue, and then rotate the queue (pop and re-add) N-1 times so the newly added element is now at the front. This avoids needing a second queue temporarily.

⏱ O(N) for push, O(1) for others💾 O(N)

Detailed Dry Run

Operation	Value	Queue State	Action
push	1	`[1]`	Add 1
push	2	`[1, 2]` -> `[2, 1]`	Add 2, rotate 1 element
pop	-	`[1]`	Pop front (2)
empty	-	`[1]`	Check if empty

java

import java.util.*;

class MyStack {
    private Queue<Integer> q = new LinkedList<>();
    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; i++) q.add(q.remove());
    }
    public int pop() { return q.remove(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /.

Visual Representation

Tokens: ["2", "1", "+", "3", "*"]

Token "2": Push. Stack: [2]
Token "1": Push. Stack: [2, 1]
Token "+": Pop 1, Pop 2. Res = 2 + 1 = 3. Push. Stack: [3]
Token "3": Push. Stack: [3, 3]
Token "*": Pop 3, Pop 3. Res = 3 * 3 = 9. Push. Stack: [9]

Result: 9

Medium

Examples

Input: tokens = ["2","1","+","3","*"]
Output: 9
((2 + 1) * 3) = 9

Approach 1

Level I: Brute Force (Recursive Evaluation)

Intuition

Without knowing the stack trick, one naive approach is to scan the token list for an operator, evaluate the two preceding operands, replace those three tokens with the result, and repeat until one token remains. This is simpler to reason about but requires repeated passes over the list.

⏱ O(N^2) because for each of the N tokens that is an operator, we scan back to find the two operands.💾 O(N) for the mutable token list copy.

java

import java.util.*;

public class Main {
    public static int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        while (list.size() > 1) {
            for (int i = 0; i < list.size(); i++) {
                String t = list.get(i);
                if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
                    int a = Integer.parseInt(list.get(i - 2));
                    int b = Integer.parseInt(list.get(i - 1));
                    int res = 0;
                    if (t.equals("+")) res = a + b;
                    else if (t.equals("-")) res = a - b;
                    else if (t.equals("*")) res = a * b;
                    else res = a / b;
                    list.set(i - 2, String.valueOf(res));
                    list.remove(i - 1);
                    list.remove(i - 1);
                    break;
                }
            }
        }
        return Integer.parseInt(list.get(0));
    }

    public static void main(String[] args) {
        System.out.println(evalRPN(new String[]{"2","1","+","3","*"})); // 9
    }
}

Approach 2

Level III: Optimal (Stack Evaluation)

Intuition

Use a stack to store operands. When an operator is encountered, pop the top two operands, apply the operator, and push the result back. This naturally handles the postfix order without parentheses.

⏱ O(N)💾 O(N)

Detailed Dry Run

Token	Action	Stack Status	Calculated
"2"	Push	`[2]`	-
"1"	Push	`[2, 1]`	-
"+"	Pop, Pop, Add	`[3]`	2 + 1 = 3
"3"	Push	`[3, 3]`	-
"*"	Pop, Pop, Mul	`[9]`	3 * 3 = 9

java

import java.util.Stack;

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String s : tokens) {
            if ("+-*/".contains(s) && s.length() == 1) {
                int b = stack.pop(), a = stack.pop();
                if (s.equals("+")) stack.push(a + b);
                else if (s.equals("-")) stack.push(a - b);
                else if (s.equals("*")) stack.push(a * b);
                else stack.push(a / b);
            } else stack.push(Integer.parseInt(s));
        }
        return stack.pop();
    }

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

⚠️ Common Pitfalls & Tips

Be mindful of integer division in Python (int(a/b)) and JavaScript (Math.trunc(a/b)), as they must truncate toward zero.

Daily Temperatures

Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day, keep answer[i] == 0.

Visual Representation

temps = [73, 74, 75, 71, 69, 72, 76, 73]

Stack (indices of waiting days):
i=0 (73): Push 0. Stack: [0]
i=1 (74): 74 > 73. Pop 0, ans[0]=1-0=1. Push 1. Stack: [1]
i=2 (75): 75 > 74. Pop 1, ans[1]=2-1=1. Push 2. Stack: [2]
i=3 (71): Push 3. Stack: [2, 3]
i=4 (69): Push 4. Stack: [2, 3, 4]
i=5 (72): 72 > 69. Pop 4, ans[4]=1. 72 > 71. Pop 3, ans[3]=2. Stack: [2, 5]
i=6 (76): 76 > 72. Pop 5, ans[5]=1. 76 > 75. Pop 2, ans[2]=4. Stack: [6]

Medium

Examples

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each day, simply look ahead to the right to find the first day with a higher temperature. This is the most natural approach but is slow for large inputs.

⏱ O(N^2) — for each of the N temperatures, we may scan up to N days forward.💾 O(1) excluding the output array.

java

import java.util.Arrays;

public class Solution {
    public int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temps[j] > temps[i]) {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
    }
}

Approach 2

Level III: Optimal (Monotonic Stack)

Intuition

Use a stack to store indices of temperatures that haven't found a warmer day yet. As we iterate, if the current temperature is warmer than the temperature at the index on top of the stack, we've found our 'warmer day' for that index. This efficiently ensures each element is pushed/popped once.

⏱ O(N)💾 O(N)

Detailed Dry Run

i	Temp	Action	Stack Status	ans[idx]
3	71	Push	`[2, 3]`	-
4	69	Push	`[2, 3, 4]`	-
5	72	Pop 4, Pop 3	`[2, 5]`	ans[4]=1, ans[3]=2
6	76	Pop 5, Pop 2	`[6]`	ans[5]=1, ans[2]=4

java

import java.util.Stack;
import java.util.Arrays;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                result[idx] = i - idx;
            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] res = sol.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
        System.out.println(Arrays.toString(res)); // [1,1,4,2,1,1,0,0]
    }
}

⚠️ Common Pitfalls & Tips

Remember that the stack should store indices, not values, so you can calculate the distance between days.

Next Greater Element I

Find the next greater element for each element in nums1 within nums2. The next greater element of x in nums2 is the first element to its right that is larger than x.

Visual Representation

nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Processing nums2 to find next greater:
1. 1: Stack [1]
2. 3: 3 > 1. Map[1]=3. Pop, Push 3. Stack [3]
3. 4: 4 > 3. Map[3]=4. Pop, Push 4. Stack [4]
4. 2: 2 < 4. Push 2. Stack [4, 2]

Result Map: {1:3, 3:4}
For nums1: 4 -> -1, 1 -> 3, 2 -> -1
Output: [-1, 3, -1]

Easy

Examples

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each element in nums1, find its position in nums2, then linearly scan rightward to find the first element greater than it. Simple, but performs redundant scans.

⏱ O(M * N) where M is nums1.length and N is nums2.length.💾 O(1) excluding the output array.

java

import java.util.Arrays;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = -1;
            boolean found = false;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) found = true;
                else if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2})));
    }
}

Approach 2

Level II: Pre-located Search (Map + Scan)

Intuition

Instead of linearly searching for each element of nums1 in nums2 every time, we can pre-store the indices of all elements in nums2 in a hash map. This allows us to jump directly to the correct starting point in nums2 for the scan, eliminating the 'find index' part of the brute force.

⏱ O(N + M*N) worst case, but faster in practice.💾 O(N) to store indices of nums2.

java

import java.util.*;
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) map.put(nums2[i], i);
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = -1;
            int start = map.get(nums1[i]);
            for (int j = start + 1; j < nums2.length; j++) {
                if (nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Monotonic Stack + HashMap)

Intuition

Use a monotonic decreasing stack to find the next greater element for all elements in nums2 in a single pass. Store the results in a hash map for O(1) lookups when processing nums1.

⏱ O(N + M) where N is nums2.length, M is nums1.length💾 O(N)

Detailed Dry Run

Num (nums2)	Stack	Map Update	Action
1	`[1]`	-	Push
3	`[3]`	1 -> 3	Pop 1, Push 3
4	`[4]`	3 -> 4	Pop 3, Push 4
2	`[4, 2]`	-	Push

java

import java.util.*;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) map.put(stack.pop(), num);
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) res[i] = map.getOrDefault(nums1[i], -1);
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] res = sol.nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
        System.out.println(Arrays.toString(res)); // [-1, 3, -1]
    }
}

⚠️ Common Pitfalls & Tips

Ensure nums1 is actually a subset of nums2 as per problem constraints. The stack approach only works for finding the next greater element.

Next Greater Element II

Given a circular integer array nums, return the next greater number for every element. Circularly means after the last element, we search from the beginning.

Visual Representation

nums = [1, 2, 1]

Pass 1:
1. Index 0 (1): Stack [0]
2. Index 1 (2): 2 > 1. ans[0]=2. Pop 0, Push 1. Stack [1]
3. Index 2 (1): 1 < 2. Push 2. Stack [1, 2]

Pass 2 (Circular):
4. i=0 (1): 1 < 1 (top). Skip.
5. i=1 (2): 2 > 1 (top). ans[2]=2. Pop 2. Stack [1]

Final Result: [2, -1, 2]

Medium

Examples

Input: nums = [1,2,1]
Output: [2,-1,2]

Approach 1

Level I: Brute Force (Double Pass Circular Scan)

Intuition

For each element, simulate the circular search by iterating up to 2N positions using modulo. When we find the first element greater than the current one, store the distance. This is straightforward but slower.

⏱ O(N^2) — for each of the N elements, we scan up to N positions circularly.💾 O(1) excluding the output array.

java

import java.util.Arrays;

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int idx = (i + j) % n;
                if (nums[idx] > nums[i]) { res[i] = nums[idx]; break; }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().nextGreaterElements(new int[]{1,2,1})));
    }
}

Approach 2

Level II: Circular Brute Force (Modulo Operator)

Intuition

Instead of two physical passes or flattening the array, we can use the modulo operator % to wrap around. For each element at index i, we check elements from (i+1) % n to (i + n - 1) % n. This is the same complexity as Level I but emphasizes the use of modular arithmetic for circular data structures.

⏱ O(N^2)💾 O(1) excluding output array.

java

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = -1;
            for (int k = 1; k < n; k++) {
                if (nums[(i + k) % n] > nums[i]) {
                    res[i] = nums[(i + k) % n];
                    break;
                }
            }
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Monotonic Stack, Double Pass)

Intuition

To handle the circularity, we can conceptually concatenate the array with itself. In practice, we iterate from 0 to 2N-1 and use modulo i % N to access elements. A monotonic stack stores indices of elements looking for their next greater neighbor.

⏱ O(N)💾 O(N)

Detailed Dry Run

i	i % N	Val	Stack	ans Update
0	0	1	`[0]`	-
1	1	2	`[1]`	ans[0]=2
2	2	1	`[1, 2]`	-
3	0	1	`[1, 2]`	-
4	1	2	`[1]`	ans[2]=2

java

import java.util.*;

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n * 2; i++) {
            while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
                res[stack.pop()] = nums[i % n];
            }
            if (i < n) stack.push(i);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.nextGreaterElements(new int[]{1,2,1}))); // [2, -1, 2]
    }
}

⚠️ Common Pitfalls & Tips

Modding i % n is essential for circular behavior. Only push to the stack in the first pass i < n to avoid infinite loops or duplicates.

Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Visual Representation

heights = [2, 1, 5, 6, 2, 3]

Processing:
1. 2: Stack [2]
2. 1: 1 < 2. Pop 2. Area = 2 * (1) = 2. Push 1.
3. 5: 5 > 1. Push 5.
4. 6: 6 > 5. Push 6.
5. 2: 2 < 6. Pop 6. Area = 6 * (1) = 6. 
     2 < 5. Pop 5. Area = 5 * (2) = 10.
     Push 2.
...
Max Area: 10 (from heights 5 and 6)

Hard

Examples

Input: heights = [2,1,5,6,2,3]
Output: 10

Approach 1

Level I: Brute Force (All Pairs)

Intuition

For every possible pair of bars (i, j), the height of the rectangle is determined by the shortest bar between them. Calculate the area for all such pairs and track the maximum.

⏱ O(N^2)💾 O(1)

java

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

Approach 2

Level III: Optimal (Monotonic Stack)

Intuition

As we iterate through the heights, we maintain a monotonic increasing stack of indices. If the current bar is shorter than the bar at the stack top, the stack top's rectangle is limited by the current bar. We pop the stack top and calculate its area: the width is the distance between the current index and the new stack top's index.

⏱ O(N)💾 O(N)

Detailed Dry Run

i	h[i]	Stack	Action	Area Calculation
0	2	`[0]`	Push	-
1	1	`[1]`	Pop 0	h[0]=2, w=1-0=1, Area=2
2	5	`[1, 2]`	Push	-
3	6	`[1, 2, 3]`	Push	-
4	2	`[1, 4]`	Pop 3, 2	h[3]=6, w=4-2-1=1, A=6; h[2]=5, w=4-1-1=2, A=10

java

import java.util.Stack;
public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int h = heights[stack.pop()];
                int w = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            int h = heights[stack.pop()];
            int w = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        return maxArea;
    }
}

Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Visual Representation

Matrix:
[ ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"] ]

Row 0: [1, 0, 1, 0, 0] -> Hist Max: 1
Row 1: [2, 0, 2, 1, 1] -> Hist Max: 2
Row 2: [3, 1, 3, 2, 2] -> Hist Max: 6 (The answer)
Row 3: [4, 0, 0, 3, 0] -> Hist Max: 4

Hard

Examples

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6

Approach 1

Level III: Optimal (Histogram per Row)

Intuition

This problem is a 2D extension of 'Largest Rectangle in Histogram'. We can treat each row as the base of a histogram where the 'height' of each column is the number of consecutive 1's above it. For each row, we maintain these heights and call the histogram function to find the max rectangle at that row.

⏱ O(Rows * Cols)💾 O(Cols)

java

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (char[] row : matrix) {
            for (int i = 0; i < row.length; i++) {
                heights[i] = row[i] == '1' ? heights[i] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
    // reused logic from Largest Rectangle in Histogram
    private int largestRectangleArea(int[] heights) { ... }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Visual Representation

heights = [0, 1, 0, 2]

1. Index 0 (0): Push 0.
2. Index 1 (1): 1 > 0. Pop 0. Stack empty. Push 1.
3. Index 2 (0): 0 < 1. Push 2.
4. Index 3 (2): 2 > 0. Pop 2 (bottom). Top is 1 (left wall).
   - height = min(2, 1) - 0 = 1
   - width = 3 - 1 - 1 = 1
   - Water = 1 * 1 = 1

Hard

Examples

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Approach 1

Level III: Optimal (Monotonic Stack)

Intuition

Use a stack to keep track of indices of bars in decreasing order of height. When we see a bar taller than the top of the stack, it means the bar at the top can trap water. The water level is limited by the current bar and the bar before the stack top (new top).

⏱ O(N)💾 O(N)

java

import java.util.Stack;
public class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0, current = 0;
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int boundedHeight = Math.min(height[current], height[stack.peek()]) - height[top];
                water += distance * boundedHeight;
            }
            stack.push(current++);
        }
        return water;
    }
}

Simplify Path

Given a Unix-style absolute path, simplify it to its canonical form.

Visual Representation

path = "/home//foo/../bar/"

Tokens: ["home", "", "foo", "..", "bar"]

1. "home": Valid name. Push. Stack: ["home"]
2. "": Empty. Skip.
3. "foo": Valid name. Push. Stack: ["home", "foo"]
4. "..": Parent dir. Pop. Stack: ["home"]
5. "bar": Valid name. Push. Stack: ["home", "bar"]

Canonical Path: "/home/bar"

Medium

Examples

Input: path = "/home//foo/"
Output: "/home/foo"

Input: path = "/../"
Output: "/"

Approach 1

Level I: Iterative Stack Processing (Natural Approach)

Intuition

Split the path by '/' into parts. Maintain a list acting as a stack: push valid directory names, pop for '..', skip '.' and empty parts. Join the stack with '/' prefixed by '/'.

⏱ O(N)💾 O(N)

java

import java.util.*;
public class Main {
    public static String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) { if (!stack.isEmpty()) stack.pollLast(); }
            else if (!s.isEmpty() && !s.equals(".")) stack.addLast(s);
        }
        return "/" + String.join("/", stack);
    }
    public static void main(String[] args) { System.out.println(simplifyPath("/home//foo/../bar/")); }
}

Approach 2

Level II: Recursive Path Reduction

Intuition

Instead of using an explicit stack, we can process the path string repeatedly by removing the most 'reducible' parts. For example, replacing /./ with / and /directory_name/../ with /. This is less efficient but helpful for understanding the underlying LIFO structure of the path.

⏱ O(N^2) in the worst case (e.g., /a/a/a/a/../../../../)💾 O(N) for string copies during reduction.

java

public class Solution {
    public String simplifyPath(String path) {
        path = path.replaceAll("/+", "/");
        if (path.length() > 1 && path.endsWith("/")) path = path.substring(0, path.length() - 1);
        
        String oldPath = "";
        while (!path.equals(oldPath)) {
            oldPath = path;
            path = path.replaceAll("/[^/]+/\\.\\.(/|$)", "/");
            path = path.replaceAll("/\\.(/|$)", "/");
        }
        if (path.isEmpty()) return "/";
        if (path.length() > 1 && path.endsWith("/")) path = path.substring(0, path.length() - 1);
        if (!path.startsWith("/")) path = "/" + path;
        return path;
    }
}

Approach 3

Level III: Optimal (Stack Tokenization)

Intuition

Split the path by / and process each component. A stack maintains the valid directory structure. .. removes the last added directory, while . or empty strings are ignored. Any other string is a valid directory to be pushed.

⏱ O(N)💾 O(N)

Detailed Dry Run

Part	Action	Stack Content
"home"	Push	`["home"]`
"foo"	Push	`["home", "foo"]`
".."	Pop	`["home"]`
"bar"	Push	`["home", "bar"]`

java

import java.util.*;

public class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else if (!s.equals("") && !s.equals(".")) {
                stack.push(s);
            }
        }
        if (stack.isEmpty()) return "/";
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) res.append("/").append(stack.removeLast());
        return res.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.simplifyPath("/home//foo/../bar/")); // "/home/bar"
    }
}

⚠️ Common Pitfalls & Tips

Multiple slashes become one. .. at the root keeps you at the root. The trailing slash should be removed unless it's the root itself.

Generate Parentheses

The Catalan Connection

The number of valid strings with n pairs of parentheses is the n-th Catalan Number: $C_n = \frac{1}{n+1} \binom{2n}{n}$ . This grows roughly as $4^n / (n \sqrt{n})$ .

Validity Conditions

A prefix of a parenthesis string is valid if and only if:

Balance: At any point, the number of closing brackets ) does not exceed the number of opening brackets (.
Target: The total number of opening brackets does not exceed n.
Finality: The total length is 2n and the final counts of ( and ) are equal.

Search Space Pruning

Instead of generating all $2^{2n}$ sequences and checking them, we only explore branches that satisfy the balance conditions.

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Medium

Examples

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Approach 1

Level I: Brute Force (Generate and Validate)

Intuition

Generate all possible strings of length 2n consisting of '(' and ')'. Check each string for validity using a stack or a counter.

Use recursion to generate all $2^{2n}$ sequences. For each sequence, verify if the balance ever goes negative and ends at zero.

⏱ O(2^{2n} * n)💾 O(n) for recursion depth.

Detailed Dry Run

n=1 Sequences: "((" (Invalid), "()" (Valid), ")(" (Invalid), "))" (Invalid).

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) result.add(new String(current));
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }
    private boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') balance++; else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
}

Approach 2

Level II: Optimized Backtracking (Keeping Balance)

Intuition

Only add a parenthesis if it keeps the sequence valid. We only add '(' if we haven't used n of them, and only add ')' if the number of ')' is less than the number of '('.

Maintain open and close counts. If open < n, we can branch with '('. If close < open, we can branch with ')'.

⏱ O(4^n / \sqrt{n})💾 O(n) recursion depth.

Detailed Dry Run

n=2

"(" (open=1, close=0)
- "((" (open=2, close=0)
  - "(()" (open=2, close=1)
    - "(())" (open=2, close=2) -> SUCCESS
- "()" (open=1, close=1)
  - "()(" (open=2, close=1)
    - "()()" (open=2, close=2) -> SUCCESS

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }
    private void backtrack(List<String> res, StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append('('); backtrack(res, sb, open + 1, close, n); sb.setLength(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')'); backtrack(res, sb, open, close + 1, n); sb.setLength(sb.length() - 1);
        }
    }
}

Approach 3

Level III: Closure Number (Divide and Conquer)

Intuition

Every non-empty valid string S can be uniquely written as (A)B, where A and B are valid (potentially empty) parenthesis strings.

To generate all strings of length 2n, we iterate over all possible lengths of A. For a fixed i, where i is the number of pairs in A, we have n-i-1 pairs in B.

⏱ O(4^n / \sqrt{n})💾 O(4^n / \sqrt{n})

Detailed Dry Run

n=2

i=0: (empty) B where B is len 1. Results: "()()"
i=1: (len 1) empty. Results: "(())"

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            res.add("");
        } else {
            for (int i = 0; i < n; i++) {
                for (String left : generateParenthesis(i)) {
                    for (String right : generateParenthesis(n - i - 1)) {
                        res.add("(" + left + ")" + right);
                    }
                }
            }
        }
        return res;
    }
}

Asteroid Collision

Calculate the final state of asteroids after all possible collisions. Positive integers move right, negative move left. If two asteroids meet, the smaller one explodes. If they are the same size, both explode.

Visual Representation

asteroids = [5, 10, -5]

1. 5: Push. Stack: [5]
2. 10: Push (same direction). Stack: [5, 10]
3. -5: Moves left. 10 > |-5|. -5 explodes. 

Final State: [5, 10]

Medium

Examples

Input: asteroids = [5,10,-5]
Output: [5,10]

Approach 1

Level I: Brute Force (Repeated Simulation)

Intuition

Repeatedly scan the list for the first pair of adjacent asteroids that collide (positive followed immediately by negative). Resolve it and restart from the beginning. Repeat until no more collisions exist.

⏱ O(N^2)💾 O(N)

java

import java.util.*;
public class Main {
    public static int[] asteroidCollision(int[] asteroids) {
        List<Integer> list = new ArrayList<>();
        for (int a : asteroids) list.add(a);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < list.size() - 1; i++) {
                int a = list.get(i), b = list.get(i + 1);
                if (a > 0 && b < 0) {
                    if (Math.abs(a) > Math.abs(b)) list.remove(i + 1);
                    else if (Math.abs(a) < Math.abs(b)) list.remove(i);
                    else { list.remove(i); list.remove(i); }
                    changed = true; break;
                }
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    public static void main(String[] args) { System.out.println(Arrays.toString(asteroidCollision(new int[]{5, 10, -5}))); }
}

Approach 2

Level III: Optimal (Stack Simulation)

Intuition

Use a stack to track asteroids moving right. When a left-moving asteroid appears, it collides with right-moving ones on the stack top. Continue popping from the stack as long as the right-moving asteroid is smaller. Handle tie-breaks where both explode.

⏱ O(N)💾 O(N)

Detailed Dry Run

Ast	Action	Stack Status	Collision Result
5	Push	`[5]`	-
10	Push	`[5, 10]`	-
-5	Compare	`[5, 10]`	-5 explodes (10 > 5)
-12	Compare	`[]`	10 explodes, 5 explodes, -12 stays

java

import java.util.*;

public class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            boolean exploded = false;
            while (!stack.isEmpty() && a < 0 && stack.peek() > 0) {
                if (stack.peek() < -a) {
                    stack.pop();
                    continue;
                } else if (stack.peek() == -a) {
                    stack.pop();
                }
                exploded = true;
                break;
            }
            if (!exploded) stack.push(a);
        }
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.asteroidCollision(new int[]{5,10,-5}))); // [5, 10]
    }
}

⚠️ Common Pitfalls & Tips

Be careful handle the case where a left-moving asteroid destroys everything in the stack and still survives. Also, ensure tie-cases (same size) are handled correctly.

Remove All Adjacent Duplicates in String II

Repeatedly remove k adjacent and equal characters from string s until no more such removals are possible.

Visual Representation

s = "deeedbbcccbdaa", k = 3

1. Process 'd': Stack [(d, 1)]
2. Process 'e': Stack [(d, 1), (e, 1)]
3. Process 'e': Stack [(d, 1), (e, 2)]
4. Process 'e': Stack [(d, 1), (e, 3)] -> Count=3! Pop (e).
5. Process 'd': Stack [(d, 2)]
...
Result: "aa"

Medium

Examples

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"

Approach 1

Level I: Brute Force (Repeated Removal)

Intuition

Repeatedly scan the string, looking for any group of k consecutive identical characters. When found, remove them and restart the scan. Repeat until no more groups of k are found. This is slow but conceptually simple.

⏱ O(N^2 / k) — Each scan is O(N) and each removal reduces the string by k characters.💾 O(N) for the working string.

java

public class Main {
    public static String removeDuplicates(String s, int k) {
        boolean changed = true;
        while (changed) {
            changed = false;
            int i = 0;
            while (i < s.length()) {
                int j = i;
                while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
                if (j - i >= k) {
                    s = s.substring(0, i) + s.substring(j);
                    // Trim multiples of k
                    int excess = (j - i) % k;
                    if (excess > 0) {
                        s = s.substring(0, i) + s.charAt(i-1-(j-i-excess)) + s.substring(i);
                    }
                    changed = true;
                    break;
                }
                i++;
            }
        }
        return s;
    }
    public static void main(String[] args) {
        System.out.println(removeDuplicates("deeedbbcccbdaa", 3)); // "aa"
    }
}

Approach 2

Level III: Optimal (Stack of Char-Count Pairs)

Intuition

Use a stack to keep track of characters and their contiguous counts. When the next character matches the top of the stack, increment the top's count. If it matches k, pop it. If it doesn't match, push a new pair (char, 1).

⏱ O(N)💾 O(N)

Detailed Dry Run

Char	Action	Stack (Top Pair)	Length
'd'	Push	`(d, 1)`	1
'e'	Push	`(e, 1)`	2
'e'	Incr	`(e, 2)`	2
'e'	Pop	-	1

java

import java.util.*;

public class Solution {
    class Node {
        char c; int count;
        Node(char c, int count) { this.c = c; this.count = count; }
    }
    public String removeDuplicates(String s, int k) {
        Stack<Node> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek().c == c) {
                stack.peek().count++;
                if (stack.peek().count == k) stack.pop();
            } else stack.push(new Node(c, 1));
        }
        StringBuilder sb = new StringBuilder();
        for (Node node : stack) {
            for (int i = 0; i < node.count; i++) sb.append(node.c);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.removeDuplicates("deeedbbcccbdaa", 3)); // "aa"
    }
}

⚠️ Common Pitfalls & Tips

Ensure the stack stores pairs so you don't have to pop characters one by one. Rebuilding the string efficiently at the end is also key.

Online Stock Span

Calculate the 'span' of a stock's price today: the number of consecutive days (including today) the price was less than or equal to today's price.

Visual Representation

Prices: [100, 80, 60, 70, 60, 75, 85]

100: Push (100, 1). Stack: [(100, 1)]
80: Push (80, 1).  Stack: [(100, 1), (80, 1)]
70: Pop 60(1). Push (70, 2). Stack: [(100, 1), (80, 1), (70, 2)]
75: Pop 60(1), 70(2). Push (75, 4). Stack: [(100, 1), (80, 1), (75, 4)]

Medium

Examples

Input: ["StockSpanner","next","next","next","next","next","next","next"]\n[[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]

Approach 1

Level I: Brute Force (Linear Lookback per Query)

Intuition

For each new price, scan backwards through all previous prices and count consecutive days where price <= today's price. Stop as soon as a higher price is found.

⏱ O(N^2) across all calls💾 O(N)

java

import java.util.*;
class StockSpanner {
    private List<Integer> prices = new ArrayList<>();
    public int next(int price) {
        prices.add(price);
        int span = 1;
        for (int i = prices.size()-2; i >= 0; i--) {
            if (prices.get(i) <= price) span++;
            else break;
        }
        return span;
    }
    public static void main(String[] args) {
        StockSpanner ss = new StockSpanner();
        int[] p = {100, 80, 60, 70, 60, 75, 85};
        for (int x : p) System.out.print(ss.next(x) + " "); // 1 1 1 2 1 4 6
    }
}

Approach 2

Level III: Optimal (Monotonic Decreasing Stack)

Intuition

Use a stack to store pairs of (price, span). When a new price is added, pop all elements with price less than or equal to the current one, adding their spans to the current span before pushing it onto the stack.

⏱ O(1) amortized per next call💾 O(N)

Detailed Dry Run

price	Action	Stack Status	Span Output
100	Push	`[(100, 1)]`	1
80	Push	`[(100, 1), (80, 1)]`	1
70	Pop 60(1)	`[(100, 1), (80, 1), (70, 2)]`	2
85	Pop 75, 80	`[(100, 1), (85, 6)]`	6

java

import java.util.*;

class StockSpanner {
    Stack<int[]> stack = new Stack<>();
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) span += stack.pop()[1];
        stack.push(new int[]{price, span});
        return span;
    }

    public static void main(String[] args) {
        StockSpanner ss = new StockSpanner();
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        for (int p : prices) System.out.print(ss.next(p) + " "); // 1 1 1 2 1 4 6 
    }
}

⚠️ Common Pitfalls & Tips

Be sure to store the accumulated span span += stack.pop()[1] so that the current element captures all smaller previous spans in constant time.

Validate Stack Sequences

Determine if a sequence of indices popped could have resulted from a sequence of pushed operations on an empty stack.

Visual Representation

pushed = [1, 2, 3], popped = [2, 3, 1]

1. Push 1: Stack [1]
2. Push 2: Stack [1, 2]. Top 2 == popped[0]. Pop. Stack [1]
3. Push 3: Stack [1, 3]. Top 3 == popped[1]. Pop. Stack [1]
4. No more pushes. Top 1 == popped[2]. Pop. Stack []

Result: True

Medium

Examples

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

Approach 1

Level I: Brute Force (Try All Push/Pop Orders)

Intuition

Without insight, we could try all possible sequences of push/pop operations on pushed[] to check if any of them matches popped[]. However, given that each element must be pushed exactly once, the simulation approach is actually already optimal in practice. The 'brute force' here is to consider a naive simulation without the greedy insight.

⏱ O(N) — same as the optimal, as the greedy simulation is the most natural approach.💾 O(N) for the stack.

java

import java.util.Stack;

public class Main {
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int popIdx = 0;
        for (int val : pushed) {
            stack.push(val);
            // Pop as much as possible
            while (!stack.isEmpty() && stack.peek() == popped[popIdx]) {
                stack.pop();
                popIdx++;
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(validateStackSequences(new int[]{1,2,3}, new int[]{2,3,1}));
    }
}

Approach 2

Level III: Optimal (Greedy Simulation)

Intuition

Iterate through the pushed array and push each element onto a stack. After each push, greedily pop elements from the stack as long as the stack top matches the current element in the popped array.

⏱ O(N)💾 O(N)

Detailed Dry Run

Push	Stack	Popped Pointer	Action
1	`[1]`	0	Push
2	`[1, 2]`	0	Push
-	`[1]`	1 (2 matched)	Pop
3	`[1, 3]`	1	Push
-	`[]`	3 (3 then 1 matched)	Pop, Pop

java

import java.util.*;

public class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validateStackSequences(new int[]{1,2,3}, new int[]{2,3,1})); // true
    }
}

⚠️ Common Pitfalls & Tips

All elements in pushed and popped are distinct as per standard constraints. Ensure you pop as many matching elements as possible after each push.

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string containing non-negative integers, +, -, *, / operators and empty spaces.

Visual Representation

s = "3+2*2"

'3': num = 3
'+': Push 3. num = 0, sign = '+'
'2': num = 2
'*': 2*2 = 4 (High precedence). 
Result: 3 + 4 = 7

Medium

Examples

Input: s = "3+2*2"
Output: 7

Approach 1

Level I: Brute Force (Two-Pass: First Handle *, / Then +, -)

Intuition

Without a stack, we can handle operator precedence in two passes: First, scan for * and / and evaluate them in-place (replacing the two operands and the operator with the result). Then, sum all remaining numbers separated by + and -. This avoids the stack but requires two traversals.

⏱ O(N) — two linear passes over the token list.💾 O(N) to store the parsed tokens.

java

import java.util.*;

public class Main {
    public static int calculate(String s) {
        s = s.replaceAll(" ", "");
        // Tokenize
        List<String> tokens = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int j = i;
                while (j < s.length() && Character.isDigit(s.charAt(j))) j++;
                tokens.add(s.substring(i, j))
;               i = j;
            } else {
                tokens.add(String.valueOf(s.charAt(i++)));
            }
        }
        // Pass 1: * and /
        int j = 0;
        while (j < tokens.size()) {
            if (tokens.get(j).equals("*") || tokens.get(j).equals("/")) {
                long a = Long.parseLong(tokens.get(j-1)), b = Long.parseLong(tokens.get(j+1));
                long res = tokens.get(j).equals("*") ? a * b : a / b;
                tokens.set(j-1, String.valueOf(res));
                tokens.remove(j); tokens.remove(j);
            } else j++;
        }
        // Pass 2: + and -
        long result = Long.parseLong(tokens.get(0));
        j = 1;
        while (j < tokens.size()) {
            long num = Long.parseLong(tokens.get(j+1));
            if (tokens.get(j).equals("+")) result += num;
            else result -= num;
            j += 2;
        }
        return (int)result;
    }
    public static void main(String[] args) {
        System.out.println(calculate("3+2*2")); // 7
    }
}

Approach 2

Level III: Optimal (Single Stack Simulation)

Intuition

Use a stack to store values. For + and -, push the number (negatively for -). For * and /, pop the last value, perform the operation with the current number, and push it back. Finally, sum the stack.

⏱ O(N)💾 O(N)

Detailed Dry Run

Char	Num	Sign	Stack	Action
'3'	3	'+'	`[]`	-
'+'	0	'+'	`[3]`	Push 3
'2'	2	'+'	`[3]`	-
'*'	0	'*'	`[3]`	-
'2'	2	'*'	`[3]`	-
End	-	-	`[3, 4]`	Pop 2, Push 2*2

java

import java.util.*;

public class Solution {
    public int calculate(String s) {
        if (s == null || s.isEmpty()) return 0;
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
                if (sign == '+') stack.push(num);
                if (sign == '-') stack.push(-num);
                if (sign == '*') stack.push(stack.pop() * num);
                if (sign == '/') stack.push(stack.pop() / num);
                sign = c;
                num = 0;
            }
        }
        int res = 0;
        for (int i : stack) res += i;
        return res;
    }

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

⚠️ Common Pitfalls & Tips

Division should truncate toward zero. Be careful with spaces and multi-digit numbers. Handle the last number in the string properly.

Decode String

Decode an encoded string where k[encoded_string] means encoded_string is repeated k times.

Visual Representation

s = "3[a]2[bc]"

'3': k = 3
'[': Push 3, Push "". Stack: [(3, "")]
'a': curr = "a"
']': Pop 3. res = "" + "a"*3 = "aaa"
'2': k = 2
'[': Push 2, Push "aaa". Stack: [(2, "aaa")]
"bc": curr = "bc"
']': Pop 2. res = "aaa" + "bc"*2 = "aaabcbc"

Medium

Examples

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Approach 1

Level I: Brute Force (Innermost Bracket First)

Intuition

Find the innermost [] bracket pair using regex or string searching, expand it (repeat the inner string by the preceding number), replace it in the original string, and repeat until no brackets remain. This naturally handles nested brackets by working from inside out.

⏱ O(N * maxK) — each pass expands one bracket group, and there can be N/2 groups.💾 O(N * maxK) for the expanded string.

java

import java.util.regex.*;

public class Main {
    public static String decodeString(String s) {
        Pattern p = Pattern.compile("(\\d+)\\[([a-z]*)\\]");
        Matcher m;
        while ((m = p.matcher(s)).find()) {
            int k = Integer.parseInt(m.group(1));
            StringBuilder rep = new StringBuilder();
            for (int i = 0; i < k; i++) rep.append(m.group(2));
            s = s.substring(0, m.start()) + rep + s.substring(m.end());
        }
        return s;
    }
    public static void main(String[] args) {
        System.out.println(decodeString("3[a]2[bc]")); // aaabcbc
    }
}

Approach 2

Level III: Optimal (Two Stacks)

Intuition

Use two stacks: one to store the multipliers (countStack) and one to store the strings built so far (resStack). When an opening bracket [ is met, push the current count and current string. When a closing bracket ] is met, pop the multiplier and the previous string, then append the repeated current string to the previous one.

⏱ O(N * maxK)💾 O(N)

Detailed Dry Run

Char	countStack	resStack	currStr
'3'	`[]`	`[]`	"" (k=3)
'['	`[3]`	`[""]`	""
'a'	`[3]`	`[""]`	"a"
']'	`[]`	`[]`	"aaa"

java

import java.util.*;

public class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> resStack = new Stack<>();
        StringBuilder cur = new StringBuilder();
        int k = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) k = k * 10 + (c - '0');
            else if (c == '[') {
                countStack.push(k);
                resStack.push(cur);
                cur = new StringBuilder();
                k = 0;
            } else if (c == ']') {
                StringBuilder tmp = cur;
                cur = resStack.pop();
                int count = countStack.pop();
                while (count-- > 0) cur.append(tmp);
            } else cur.append(c);
        }
        return cur.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.decodeString("3[a]2[bc]")); // "aaabcbc"
    }
}

⚠️ Common Pitfalls & Tips

Multi-digit numbers (like 100[a]) must be handled. Nested brackets are naturally handled by the stack.

Remove Duplicate Letters

Remove duplicate letters from string s so that every letter appears once. The result must be the smallest in lexicographical order among all possible results.

Visual Representation

s = "bcabc"

Counts: {b:2, c:2, a:1}
1. 'b': Push. Stack: [b]. Counts: {b:1, c:2, a:1}
2. 'c': Push. Stack: [b, c]. Counts: {b:1, c:1, a:1}
3. 'a': 
   - 'c' > 'a' and c's count > 0. Pop c.
   - 'b' > 'a' and b's count > 0. Pop b.
   - Push 'a'. Stack: [a]. Counts: {b:1, c:1, a:0}
4. 'b': Push. Stack: [a, b]. Counts: {b:0, c:1, a:0}
5. 'c': Push. Stack: [a, b, c]. Counts: {b:0, c:0, a:0}

Result: "abc"

Medium

Examples

Input: s = "bcabc"
Output: "abc"

Approach 1

Level I: Generate All Subsequences, Filter, Then Sort

Intuition

Generate all unique subsequences of the string that contain each character exactly once (using a set of frequency tracking). Filter to keep valid ones and return the lexicographically smallest. This is exponential and only feasible for tiny inputs.

⏱ O(2^N * N) — exponential in string length.💾 O(2^N) for storing all unique subsequences.

java

import java.util.*;

public class Main {
    static Set<String> seen = new HashSet<>();
    
    public static String removeDuplicateLetters(String s) {
        Set<Character> chars = new HashSet<>();
        for (char c : s.toCharArray()) chars.add(c);
        int n = chars.size();
        List<String> valid = new ArrayList<>();
        generateSubseqs(s, 0, "", new int[26], valid, n, new int[26]);
        Collections.sort(valid);
        return valid.get(0);
    }
    
    static void generateSubseqs(String s, int i, String cur, int[] used, List<String> valid, int targetLen, int[] freq) {
        if (cur.length() == targetLen) { valid.add(cur); return; }
        if (i == s.length()) return;
        char c = s.charAt(i);
        if (used[c - 'a'] == 0) {
            used[c - 'a'] = 1;
            generateSubseqs(s, i + 1, cur + c, used, valid, targetLen, freq);
            used[c - 'a'] = 0;
        }
        generateSubseqs(s, i + 1, cur, used, valid, targetLen, freq);
    }

    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("bcabc")); // abc
    }
}

Approach 2

Level III: Optimal (Greedy Monotonic Stack)

Intuition

Maintain a stack of characters that represents the current smallest lexicographical result. Use a frequency map to know if a character will appear later. If the current character is smaller than the stack top and the stack top appears again later, pop the stack top. Use a seen set to skip characters already in the result.

⏱ O(N)💾 O(1) - alphabet size

Detailed Dry Run

Char	Action	Stack	Seen	Count Left
'b'	Push	`[b]`	{b}	b:1
'c'	Push	`[b, c]`	{b, c}	c:1
'a'	Pop b, c; Push a	`[a]`	{a}	a:0
'b'	Push	`[a, b]`	{a, b}	b:0

java

import java.util.*;

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        boolean[] seen = new boolean[26];
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen[c - 'a']) continue;
            while (!st.isEmpty() && st.peek() > c && last[st.peek() - 'a'] > i) {
                seen[st.pop() - 'a'] = false;
            }
            st.push(c);
            seen[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (char c : st) sb.append(c);
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.removeDuplicateLetters("bcabc")); // "abc"
    }
}

⚠️ Common Pitfalls & Tips

You can only pop a character if you know it appears later in the string. Character counts or last-occurrence indices are necessary.

Basic Calculator

Implement a basic calculator to evaluate a simple expression string containing (, ), +, -, non-negative integers and empty spaces.

Visual Representation

s = " 1 + (4 + 5 - 2) - 3 "

'1': res = 1, sign = +
'+': Push current res (1) and sign (+) to stack.
'(': Start new group.
Groups: (4 + 5 - 2) = 7
Pop: 1 + (+)7 = 8
'-': res = 8, sign = -
'3': res = 8 - 3 = 5

Hard

Examples

Input: s = " 1 + (4 + 5 - 2) - 3 "
Output: 5

Approach 1

Level III: Optimal (Iterative with Stack)

Intuition

Process the string character by character. Use a stack to handle parentheses by saving the current result and sign before entering a new group. For + and -, apply them to the running total. For (, push the state; for ), pop and combine.

⏱ O(N)💾 O(N)

Detailed Dry Run

Char	Running Total	Sign	Stack
'1'	1	1	`[]`
'+'	1	1	`[]`
'('	0	1	`[(1, 1)]`
'4'	4	1	`[(1, 1)]`

java

import java.util.Stack;

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

⚠️ Common Pitfalls & Tips

Ensure the last number is added. Be careful with large results (use long long in C++). Handle nested parentheses correctly by pushing both result and sign.

Basic Calculator III

Evaluate an expression string containing (, ), +, -, *, /, non-negative integers and spaces. This is the ultimate calculator problem.

Visual Representation

s = "2*(5+5*2)/3+(6/2+8)"

Handle parentheses recursively or using a stack stack.
Within each group, apply multiply/divide first, then add/subtract.
Result: 2*(15)/3 + (11) = 10 + 11 = 21

Hard

Examples

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21

Approach 1

Level III: Optimal (Recursion with Deque/Index)

Intuition

This problem combines Basic Calculator I and II. The most natural solution uses recursion to handle parentheses: every time we see (, we recurse; every time we see ), we return the result of the current sub-expression. Within each level, we use the standard 'accumulator' logic for +, -, *, /.

⏱ O(N)💾 O(N)

java

import java.util.*;

public class Solution {
    public int calculate(String s) {
        Queue<Character> tokens = new LinkedList<>();
        for (char c : s.toCharArray()) if (c != ' ') tokens.add(c);
        tokens.add('+'); // Sentinel
        return helper(tokens);
    }

    private int helper(Queue<Character> q) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        while (!q.isEmpty()) {
            char c = q.poll();
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '(') num = helper(q);
            else {
                if (sign == '+') stack.push(num);
                if (sign == '-') stack.push(-num);
                if (sign == '*') stack.push(stack.pop() * num);
                if (sign == '/') stack.push(stack.pop() / num);
                sign = c;
                num = 0;
                if (c == ')') break;
            }
        }
        int res = 0;
        for (int i : stack) res += i;
        return res;
    }
}

⚠️ Common Pitfalls & Tips

Sentinel + at the end makes the loop logic cleaner for the last number. Be careful with division truncation in Python.

Expression Add Operators

Precedence and Multiplication

Adding + and - is straightforward: just add or subtract the current value. However, multiplication (*) has higher precedence. If we have 1 + 2 * 3, we cannot simply compute (1 + 2) * 3.

The Trick: Tracking Previous Operand

To handle prev + current * next, we need to subtract current and add current * next. Formula: NewTotal = (OldTotal - prevOperand) + (prevOperand * currentValue).

Corner Cases

Leading Zeros: A number like "05" is invalid unless it's just "0".
Overflow: Since the target and intermediate values can exceed $2^{31}-1$ , use long (64-bit integers).

Given a string num containing only digits and an integer target, return all possibilities to insert the binary operators +, -, and/or * between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Hard

Examples

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Approach 1

Level I: Basic Backtracking with Post-Evaluation

Intuition

Insert every possible operator between digits to generate all possible expressions, then evaluate each one.

Generate expressions by recursion. For each string of length $N$ , there are $4^{N-1}$ combinations. This is very slow due to the evaluation step.

⏱ O(N * 4^N)💾 O(N)

Detailed Dry Run

num="12", target=3.

Try "1+2" -> eval(3) == 3 -> SUCCESS.
Try "1-2" -> eval(-1) != 3.
Try "1*2" -> eval(2) != 3.

java

class Solution {
    // Naive version: generate all and evaluate.
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        backtrack(num, target, 1, "" + num.charAt(0), res);
        return res;
    }
    private void backtrack(String num, int target, int i, String expr, List<String> res) {
        if (i == num.length()) {
            if (evaluate(expr) == target) res.add(expr);
            return;
        }
        backtrack(num, target, i + 1, expr + "+" + num.charAt(i), res);
        backtrack(num, target, i + 1, expr + "-" + num.charAt(i), res);
        backtrack(num, target, i + 1, expr + "*" + num.charAt(i), res);
        backtrack(num, target, i + 1, expr + num.charAt(i), res);
    }
    private long evaluate(String s) { /* Standard expression eval */ return 0; }
}

Approach 2

Level II: Optimized Backtracking (Running Value)

Intuition

Calculate the expression value on the fly to avoid explicit evaluation. Handle multiplication by tracking the previous added value.

Use dfs(index, path, currentVal, prevOperand). If we add *, the new value is (currentVal - prevOperand) + (prevOperand * now).

⏱ O(4^N)💾 O(N)

Detailed Dry Run

num="123", target=6

Pick "1": val=1, prev=1.
Pick "2" with "+": val=1+2=3, prev=2.
Pick "3" with "+": val=3+3=6, prev=3. SUCCESS.
Pick "2" with "": val=(1-1)+(12)=2, prev=2.
Pick "3" with "": val=(2-2)+(23)=6, prev=6. SUCCESS.

java

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        if (num == null || num.length() == 0) return res;
        dfs(0, "", 0, 0, num, target, res);
        return res;
    }
    private void dfs(int idx, String path, long val, long prev, String num, int target, List<String> res) {
        if (idx == num.length()) {
            if (val == target) res.add(path);
            return;
        }
        for (int i = idx; i < num.length(); i++) {
            if (i > idx && num.charAt(idx) == '0') break;
            String s = num.substring(idx, i + 1);
            long now = Long.parseLong(s);
            if (idx == 0) {
                dfs(i + 1, s, now, now, num, target, res);
            } else {
                dfs(i + 1, path + "+" + s, val + now, now, num, target, res);
                dfs(i + 1, path + "-" + s, val - now, -now, num, target, res);
                dfs(i + 1, path + "*" + s, val - prev + prev * now, prev * now, num, target, res);
            }
        }
    }
}

Approach 3

Level III: Memory-Optimized Backtracking

Intuition

Instead of building string paths and then converting them, use a char[] or byte[] to build the path directly, avoiding string concatenations which are expensive.

Pass a char[] (or byte[] in Go) to the recursive function. When adding an operator or digit, update the array and its current length. Backtrack by resetting the length.

⏱ O(4^N)💾 O(N)

Detailed Dry Run

num="123", target=6

path=['1'], len=1. dfs(1, 1, 1, path)
path=['1','+','2'], len=3. dfs(2, 3, 2, path)
path=['1','+','2','+','3'], len=5. dfs(3, 6, 3, path). Target hit. Add "1+2+3" to res.
Backtrack: path=['1','+','2'], len=3. Try '*'.
path=['1','+','2','','3'], len=5. dfs(3, 1+2-2+23=7, 2*3=6, path). Target not hit.

java

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        if (num == null || num.length() == 0) return res;
        char[] path = new char[num.length() * 2];
        dfs(res, path, 0, num.toCharArray(), 0, 0, 0, target);
        return res;
    }
    private void dfs(List<String> res, char[] path, int len, char[] num, int idx, long val, long prev, int target) {
        if (idx == num.length) {
            if (val == target) res.add(new String(path, 0, len));
            return;
        }
        long now = 0;
        int pos = len;
        if (idx != 0) len++;
        for (int i = idx; i < num.length; i++) {
            if (i > idx && num[idx] == '0') break;
            now = now * 10 + (num[i] - '0');
            path[len++] = num[i];
            if (idx == 0) {
                dfs(res, path, len, num, i + 1, now, now, target);
            } else {
                path[pos] = '+'; dfs(res, path, len, num, i + 1, val + now, now, target);
                path[pos] = '-'; dfs(res, path, len, num, i + 1, val - now, -now, target);
                path[pos] = '*'; dfs(res, path, len, num, i + 1, val - prev + prev * now, prev * now, target);
            }
        }
    }
}

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.