Stack

Problem: s contains only ()[]{}. It is valid if every bracket is closed by the same type, in the correct order. Check it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · s consists of parentheses only '()[]{}'.

From brute force to the pattern: Repeatedly deleting (), [] and {} pairs from the string until nothing changes is O(n²). A stack matches each bracket once: O(n).

Spot it: "Most recent unmatched opener must close first" is last-in, first-out → a stack.

Approach:

1. Map each closer to its opener: ) → (, ] → [, } → {.
2. Push every opener.
3. For a closer: the stack must be non-empty and its top must be the matching opener; pop it. Otherwise invalid.
4. At the end, every opener must have been matched: the stack must be empty.

class Solution:
    def isValid(self, s: str) -> bool:
        opener_of = {")": "(", "]": "[", "}": "{"}
        stack = []
        for ch in s:
            if ch in opener_of:
                # a closer: it must close the most recent unmatched opener
                if not stack or stack[-1] != opener_of[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)          # an opener waits for its closer
        # leftover openers were never closed
        return len(stack) == 0

What the code is doing, line by line:

1. opener_of: for each closing bracket, the opening bracket it needs.
2. if ch in opener_of: the character is a closer.
3. if not stack or stack[-1] != opener_of[ch]: return False: nothing to close, or the wrong type on top, e.g. "(]".
4. stack.pop(): the pair is matched and removed.
5. stack.append(ch): openers wait on the stack.
6. return len(stack) == 0: "((" has no bad closer but is still invalid.

Dry run on the example:

s = "([{}])". Returns True.

ch	action	stack after
(	push	(
[	push	( [
{	push	( [ {
}	top is { → pop	( [
]	top is [ → pop	(
)	top is ( → pop	empty → True

Edge cases to test:

• Only openers, e.g. "((" → False.
• A closer first, e.g. ")(" → False.
• Interleaved types, e.g. "([)]" → False.

Complexity: O(n) time, O(n) space.

Problem: Evaluate an arithmetic expression in Reverse Polish Notation, where operators come after their two operands (["2", "1", "+", "3", "*"] means (2 + 1) * 3). Division truncates toward zero.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ tokens.length ≤ 10⁴ · tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

From brute force to the pattern: Converting back to infix and evaluating is roundabout. A stack evaluates postfix in one pass: O(n).

Spot it: In postfix, an operator always applies to the two most recent results → stack evaluation.

Approach:

1. Push numbers.
2. For an operator: pop b (the top), then a. Compute a op b (order matters for - and /) and push the result.
3. The single value left is the answer.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in ("+", "-", "*", "/"):
                b = stack.pop()       # the RIGHT operand is on top
                a = stack.pop()
                if token == "+":
                    stack.append(a + b)
                elif token == "-":
                    stack.append(a - b)
                elif token == "*":
                    stack.append(a * b)
                else:
                    # int(a / b) truncates toward zero; a // b would round down
                    stack.append(int(a / b))
            else:
                stack.append(int(token))
        return stack[0]

What the code is doing, line by line:

1. if token in ("+", "-", "*", "/"): an operator; anything else is a number (possibly negative, like "-11").
2. b = stack.pop() then a = stack.pop(): the top is the second operand. ["4", "2", "-"] means 4 − 2, not 2 − 4.
3. int(a / b): LeetCode wants truncation toward zero. Python's // floors, so -7 // 2 is -4, while int(-7 / 2) is -3.
4. return stack[0]: a valid expression leaves exactly one value.

Dry run on the example:

tokens = ["4", "13", "5", "/", "+"] (LeetCode Example 2). Returns 6 (4 + 13 / 5).

token	action	stack after
"4"	push	[4]
"13"	push	[4, 13]
"5"	push	[4, 13, 5]
"/"	int(13 / 5) = 2	[4, 2]
"+"	4 + 2 = 6	[6]

Edge cases to test:

• Negative numbers like "-11" (not an operator!).
• Division truncating toward zero, e.g. -7 / 2 → -3.
• A single number.

Complexity: O(n) time and space.

Problem: Design a stack that supports push, pop, top and getMin (the smallest element currently in the stack), all in O(1) time.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: -2³¹ ≤ val ≤ 2³¹ - 1 · Methods pop, top and getMin operations will always be called on non-empty stacks. · At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

From brute force to the pattern: Scanning the stack for the minimum is O(n) per getMin. Keeping the running minimum with every entry makes all four operations O(1).

Spot it: Popping can remove the current minimum, and then you need the previous one immediately. So remember, for every position, what the minimum was at that height: push pairs (value, min so far).

Approach:

1. Each stack entry is a pair (val, current_min).
2. push(val): the new minimum is min(val, previous min) (or val if the stack is empty).
3. pop() removes the top pair; the pair below still holds the correct minimum for the smaller stack.
4. top() and getMin() read the two halves of the top pair.

class MinStack:
    def __init__(self):
        # each entry is (value, smallest value at or below this entry)
        self.stack = []

    def push(self, val: int) -> None:
        if self.stack:
            current_min = min(val, self.stack[-1][1])
        else:
            current_min = val
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

What the code is doing, line by line:

1. self.stack: a list of tuples. self.stack[-1][0] is the top value, self.stack[-1][1] the minimum of the whole stack.
2. push: the minimum for the new height is the smaller of val and the minimum just below.
3. pop: no recomputation. The entry below already knows its own minimum.
4. top, getMin: one index each, so O(1).

Dry run on the example:

LeetCode Example 1: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() → -3, 0, -2.

call	stack after (value, min)	returns
push(-2)	(-2, -2)	—
push(0)	(-2, -2) (0, -2)	—
push(-3)	(-2, -2) (0, -2) (-3, -3)	—
getMin()	unchanged	-3
pop()	(-2, -2) (0, -2)	—
top()	unchanged	0
getMin()	unchanged	-2

Edge cases to test:

• Pushing duplicates of the minimum.
• Popping the minimum.
• Negative values.

Complexity: O(1) time for every operation, O(n) space.

Problem: Process the operations: an integer records that score; "+" records the sum of the previous two scores; "D" records double the previous score; "C" removes the previous score. Return the total.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ operations.length ≤ 1000 · operations[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 10⁴, 3 * 10⁴]. · For operation "+", there will always be at least two previous scores on the record. · For operations "C" and "D", there will always be at least one previous score on the record.

From brute force to the pattern: Keeping a plain list and re-reading it works the same way. The stack view makes it clear that only the top entries ever matter: O(n).

Spot it: Every operation refers to the most recent scores, and C undoes the last one. Recent-first access + undo = a stack.

Approach:

1. C → pop. D → push 2 × top. + → push the sum of the top two.
2. Otherwise push int(op).
3. Return the sum of the stack.

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        scores = []
        for op in operations:
            if op == "C":
                scores.pop()                         # cancel the last score
            elif op == "D":
                scores.append(2 * scores[-1])        # double the last score
            elif op == "+":
                scores.append(scores[-1] + scores[-2])
            else:
                scores.append(int(op))               # a plain number, maybe negative
        return sum(scores)

What the code is doing, line by line:

1. scores: valid scores so far; scores[-1] is the most recent and scores[-2] the one before it.
2. scores.pop(): C removes the last score as if it never happened.
3. 2 * scores[-1] and scores[-1] + scores[-2]: read the top without removing anything.
4. int(op): converts strings such as "-2" to integers.
5. sum(scores): the total of what remains.

Dry run on the example:

operations = ["5", "2", "C", "D", "+"] (LeetCode Example 1). Returns 30.

op	action	scores after
"5"	push 5	[5]
"2"	push 2	[5, 2]
"C"	pop 2	[5]
"D"	push 2 × 5	[5, 10]
"+"	push 10 + 5	[5, 10, 15] → sum 30

Edge cases to test:

• C removing the only score.
• Negative scores.
• + right after a C.

Complexity: O(n) time and space.

Problem: Decode a string encoded as k[encoded_string], where the part inside the brackets is repeated k times. Brackets can be nested, e.g. "3[a2[c]]" → "accaccacc".

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 30 · s consists of lowercase English letters, digits, and square brackets '[]'. · s is guaranteed to be a valid input. · All the integers in s are in the range [1, 300].

From brute force to the pattern: Repeatedly finding the innermost k[...] with a search and replacing it rescans the string many times: O(n²) or worse. A stack processes each character once and expands each bracket exactly when it closes.

Spot it: Nested brackets where the innermost part must be finished first, then plugged into the level around it: last opened, first closed. That's a stack, just like matching parentheses, but each level also remembers its text and its repeat count.

Why not another pattern? A single left-to-right pass with string concatenation can't handle nesting, because when an inner ] closes you need the text that was being built outside it. Recursion works too (it uses the call stack); the explicit stack shows the same idea step by step.

Key insight: Keep two things while scanning: current (the string being built at this nesting level) and number (a repeat count being read). On [ push (current, number) and start a fresh level. On ] pop (previous, k) and set current = previous + current * k.

Approach:

1. Scan characters. Digits build number (it can have several digits, e.g. 12[).
2. On [: push (current, number), then reset current = "" and number = 0 for the inner level.
3. On ]: pop (previous, k) and combine: current = previous + current * k.
4. Any other character is a letter: append it to current.
5. At the end, current is the decoded string.

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []      # (text before this bracket, how many times to repeat it)
        current = ""    # text being built at the current nesting level
        number = 0      # repeat count being read digit by digit
        for ch in s:
            if ch.isdigit():
                number = number * 10 + int(ch)  # counts can have several digits
            elif ch == "[":
                stack.append((current, number))  # save the outer level
                current = ""  # start a fresh inner level
                number = 0
            elif ch == "]":
                previous, k = stack.pop()  # back to the outer level
                current = previous + current * k  # plug in the repeated inner text
            else:
                current = current + ch  # a plain letter
        return current

What the code is doing, line by line:

1. stack: each entry remembers the outer level's text and the count for the bracket we just entered.
2. number = number * 10 + int(ch): builds multi-digit counts like 12 from '1' then '2'.
3. [: push (current, number), then clear both. The inner level starts with empty text.
4. ]: previous, k = stack.pop() restores the outer text; current * k repeats the inner text k times; previous + ... attaches it.
5. else: a letter is appended to the current level.
6. return current: after the last character we are back at the outermost level.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Multi-digit counts, e.g. "10[a]".
• Letters after a bracket, e.g. "2[abc]3[cd]ef".
• Deep nesting, e.g. "3[a2[c]]" → "accaccacc".

Complexity: O(output length) time and space: each character of the result is created once per nesting level that repeats it.

Problem: Convert an absolute Unix path into its canonical form.

Solve it on LeetCode ↗

Constraints: 1 ≤ path.length ≤ 3000 · path consists of English letters, digits, period '.', slash '/' or '_'. · path is a valid absolute Unix path.

From brute force to the pattern: Repeated string replacement is fragile; a stack of parts is one clean pass.

Spot it: Directories nest: .. undoes the most recent directory → a stack of path parts.

Why not another pattern? String replacement tricks (/./, /../) get edge cases wrong (e.g. ... is a valid name).

Approach:

1. Split by /.
2. Skip empty parts and .; .. pops if possible; anything else is pushed.
3. Join as / + /.join(stack).

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split("/"):
            if part == "" or part == ".":
                continue  # extra slashes or "current directory"
            if part == "..":
                if stack:
                    stack.pop()  # go up one level
            else:
                stack.append(part)  # a directory name (even "...")
        return "/" + "/".join(stack)

What the code is doing, line by line:

1. Multiple slashes produce empty parts, which are ignored.
2. .. at the root stays at the root.
3. Any other string, including ..., is a name.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• /../ → /.
• Trailing slash.
• Names like ....

Complexity: O(n) time and space.

Problem: Evaluate an expression with + − × / (integer division truncating toward zero) and spaces.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 3 * 10⁵ · s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces. · s represents a valid expression. · All the integers in the expression are non-negative integers in the range [0, 2³¹ - 1]. · The answer is guaranteed to fit in a 32-bit integer.

From brute force to the pattern: Multiple passes (first × ÷, then + −) with list rewriting work but are clumsier; the stack is one pass.

Spot it: Precedence: ×/÷ must happen before +/−. Keep a stack of terms: +/− push a new term; ×/÷ modify the last term. The answer is the sum.

Why not another pattern? Evaluating left to right ignores precedence.

Approach:

1. Read numbers; when an operator (or the end) arrives, apply the previous operator to num.
2. + push num, − push −num, × multiply top, / divide top (truncate).
3. Return sum(stack).

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = "+"  # operator before the current number
        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            if (ch in "+-*/") or i == len(s) - 1:
                if op == "+":
                    stack.append(num)
                elif op == "-":
                    stack.append(-num)
                elif op == "*":
                    stack.append(stack.pop() * num)  # binds tighter: apply now
                else:
                    stack.append(int(stack.pop() / num))  # truncate toward zero
                op = ch
                num = 0
        return sum(stack)

What the code is doing, line by line:

1. The operator is applied when the next operator (or the end) is reached, once its right operand is complete.
2. int(a / b) truncates toward zero, unlike // for negative numbers.
3. All remaining terms are added at the end.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Division of a negative term.
• Spaces.
• A single number.

Complexity: O(n) time and space.

Problem: Record hits at timestamps (non-decreasing) and return the number of hits in the past 300 seconds.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ timestamp ≤ 2 * 10⁹ · All the calls are made in chronological order (timestamp is monotonically increasing) · At most 300 calls will be made to hit and getHits

From brute force to the pattern: Scanning every stored hit per query is linear; dropping expired hits from a queue is amortised constant. (Follow-up: two arrays of 300 buckets give O(1) memory per second.)

Spot it: Timestamps arrive in order, so old hits are always at the front: a queue (deque). Remove expired hits from the front, the rest is the answer. (Like a monotonic stack, the order of insertion does the work.)

Why not another pattern? Storing all hits and scanning them per query is O(total hits) each time.

Approach:

1. hit(t): append t.
2. getHits(t): pop from the front while front ≤ t − 300; return the length.

from collections import deque

class HitCounter:
    def __init__(self):
        self.hits = deque()  # timestamps in arrival order

    def hit(self, timestamp: int) -> None:
        self.hits.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()  # older than 5 minutes
        return len(self.hits)

What the code is doing, line by line:

1. Expired hits are at the front because timestamps never decrease.
2. Each hit is removed at most once, so the work is amortised O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Many hits with the same timestamp.
• A query exactly 300 s later (excluded).
• No hits yet → 0.

Complexity: Amortised O(1) per call, O(hits in window) space.

Problem: Implement a fixed-capacity FIFO ring buffer with enQueue, deQueue, Front, Rear, isEmpty, isFull.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ 1000 · 0 ≤ value ≤ 1000 · At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

From brute force to the pattern: A list with pop(0) shifts every element; the ring buffer never moves data.

Spot it: A ring buffer is an array where indices wrap around. Store the head index and the count; the tail is (head + count − 1) % k.

Why not another pattern? A Python list with pop(0) is O(n) per dequeue and doesn't have a fixed capacity.

Approach:

1. enQueue: if full, false; write at (head + size) % k, size += 1.
2. deQueue: if empty, false; head = (head + 1) % k, size −= 1.
3. Front = data[head], Rear = data[(head + size − 1) % k].

class MyCircularQueue:
    def __init__(self, k: int):
        self.data = [0] * k
        self.head = 0  # index of the front element
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.size == len(self.data):
            return False
        self.data[(self.head + self.size) % len(self.data)] = value  # next free slot, wrapping
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.size == 0:
            return False
        self.head = (self.head + 1) % len(self.data)  # the front moves forward
        self.size -= 1
        return True

    def Front(self) -> int:
        return self.data[self.head] if self.size else -1

    def Rear(self) -> int:
        return self.data[(self.head + self.size - 1) % len(self.data)] if self.size else -1

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == len(self.data)

What the code is doing, line by line:

1. Keeping size avoids the classic full-vs-empty ambiguity of head/tail pointers.
2. All operations are O(1) index arithmetic.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Enqueue when full → false.
• Dequeue when empty → false.
• Wrap-around after many operations.

Complexity: O(1) per operation, O(k) space.

Problem: Given start/end logs of a single-threaded program, return each function's exclusive running time.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 100 · 2 ≤ logs.length ≤ 500 · 0 ≤ function_id < n · 0 ≤ timestamp ≤ 10⁹ · No two start events will happen at the same timestamp. · No two end events will happen at the same timestamp. · Each function has an "end" log for each "start" log.

From brute force to the pattern: Computing each call's total duration and subtracting nested calls is more complicated; charging slices to the stack top is one pass.

Spot it: Function calls nest → a stack mirrors the call stack. Time between two events belongs to whichever function is on top.

Why not another pattern? Subtracting children's durations from parents afterwards needs extra bookkeeping per call.

Approach:

1. Keep prev = the time the current slice started.
2. start at t: charge t − prev to the top (if any), push the id, prev = t.
3. end at t: charge t − prev + 1 to the top, pop, prev = t + 1.

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        result = [0] * n
        stack = []
        prev = 0  # start of the current time slice
        for log in logs:
            fid, kind, t = log.split(":")
            fid, t = int(fid), int(t)
            if kind == "start":
                if stack:
                    result[stack[-1]] += t - prev  # the caller ran until now
                stack.append(fid)
                prev = t
            else:
                result[stack.pop()] += t - prev + 1  # end times are inclusive
                prev = t + 1
        return result

What the code is doing, line by line:

1. A start pauses the current top; an end finishes it.
2. End timestamps are inclusive (the function runs through the end of that unit), hence + 1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Recursion (same id nested).
• A function that starts and ends at the same time unit.
• Single function.

Complexity: O(len(logs)) time, O(n) space.

Problem: Implement a fixed-capacity double-ended queue with inserts and deletes at both ends.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ 1000 · 0 ≤ value ≤ 1000 · At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

From brute force to the pattern: List-based front inserts are O(n); the ring buffer is O(1).

Spot it: Same ring buffer as the circular queue, but the front can also move backwards: head = (head − 1) % k.

Why not another pattern? A list with insert(0, x) is O(n) per front insert.

Approach:

1. insertFront: head = (head − 1) % k, write there.
2. insertLast: write at (head + size) % k.
3. deleteFront: head += 1; deleteLast: just size −= 1.

class MyCircularDeque:
    def __init__(self, k: int):
        self.data = [0] * k
        self.head = 0
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.head = (self.head - 1) % len(self.data)  # step back, wrapping
        self.data[self.head] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[(self.head + self.size) % len(self.data)] = value
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % len(self.data)
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.size -= 1  # the last slot is simply forgotten
        return True

    def getFront(self) -> int:
        return -1 if self.isEmpty() else self.data[self.head]

    def getRear(self) -> int:
        return -1 if self.isEmpty() else self.data[(self.head + self.size - 1) % len(self.data)]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == len(self.data)

What the code is doing, line by line:

1. Python's % returns a non-negative result, so (head − 1) % k wraps correctly.
2. Removing from the back only shrinks the size.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Full / empty checks.
• Wrap-around at index 0.
• Capacity 1.

Complexity: O(1) per operation, O(k) space.

Problem: * can be (, ) or empty. Is the string a valid parenthesis string?

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 100 · s[i] is '(', ')' or '*'.

From brute force to the pattern: Trying all star replacements is 3^k; the range is one pass. (Two stacks of indices also work in O(n).)

Spot it: A plain stack/counter would check balance; with wildcards, keep the range of possible open counts: lo (treat stars as )) and hi (treat stars as (). It's valid if hi never drops below 0 and lo can reach 0 at the end.

Why not another pattern? Trying three options for every star is 3^stars.

Approach:

1. (: lo += 1, hi += 1. ): both −1. *: lo −= 1, hi += 1.
2. If hi < 0, false. Clamp lo at 0.
3. Return lo == 0.

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0  # range of possible numbers of unmatched "("
        for ch in s:
            if ch == "(":
                lo += 1
                hi += 1
            elif ch == ")":
                lo -= 1
                hi -= 1
            else:
                lo -= 1  # star as ")"
                hi += 1  # star as "("
            if hi < 0:
                return False  # too many ")" even with every star as "("
            lo = max(lo, 0)  # can't have negative open brackets
        return lo == 0

What the code is doing, line by line:

1. Every count between lo and hi is achievable by some choice of stars.
2. Clamping lo at 0 discards choices that would make the prefix invalid.
3. At the end, 0 open brackets must be achievable.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Only stars → true.
• )( with stars around.
• Star before the ( it should close (*( is false).

Complexity: O(n) time, O(1) space.

Problem: Positive asteroids move right, negative move left; on collision the smaller explodes (equal: both). Return the survivors.

Solve it on LeetCode ↗

Constraints: 2 ≤ asteroids.length ≤ 10⁴ · -1000 ≤ asteroids[i] ≤ 1000 · asteroids[i] != 0

From brute force to the pattern: Time-step simulation is slow; the stack resolves each collision once.

Spot it: Only a left-mover meeting earlier right-movers collides, and it meets the most recent first → a stack.

Why not another pattern? Simulating step by step in time is O(n²) or worse.

Approach:

1. For each asteroid a: while a < 0 and the top is positive: compare sizes.
2. Top smaller → pop, continue; equal → pop, a dies; top bigger → a dies.
3. If a survives, push it.

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for a in asteroids:
            alive = True
            while alive and a < 0 and stack and stack[-1] > 0:  # a moving left meets one moving right
                if stack[-1] < -a:
                    stack.pop()  # the right-mover explodes; keep going
                    continue
                if stack[-1] == -a:
                    stack.pop()  # both explode
                alive = False  # a explodes
            if alive:
                stack.append(a)
        return stack

What the code is doing, line by line:

1. Right-movers and left-movers that are already past each other never collide.
2. A big left-mover may destroy several right-movers in a row.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal sizes (both explode).
• All moving the same way.
• Left-movers at the start (never collide).

Complexity: O(n) time (each asteroid pushed and popped at most once), O(n) space.

Problem: Return the minimum number of parentheses to insert so the string becomes valid.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 1000 · s[i] is either '(' or ')'.

From brute force to the pattern: Trying insertions is exponential; a counter pass is linear.

Spot it: Matching brackets is a stack; since there's one bracket type, a counter of open brackets is enough.

Why not another pattern? Trying insertions is exponential.

Approach:

1. open = unmatched ( so far; adds = inserted (.
2. ( → open += 1; ) → close one if open, else adds += 1.
3. Return adds + open.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_count = 0  # "(" waiting for a match
        adds = 0  # "(" we must insert for stray ")"
        for ch in s:
            if ch == "(":
                open_count += 1
            elif open_count:
                open_count -= 1  # matched
            else:
                adds += 1  # nothing to close: insert "(" before it
        return adds + open_count  # leftover "(" each need a ")"

What the code is doing, line by line:

1. A ) with nothing open needs an inserted (.
2. Unmatched ( at the end each need a ).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty string → 0.
• ))) → 3.
• ()))(( → 4.

Complexity: O(n) time, O(1) space.

Problem: Read numbers 1, 2, … in order; using Push/Pop on a stack, make the stack equal target. Return the operations.

Solve it on LeetCode ↗

Constraints: 1 ≤ target.length ≤ 100 · 1 ≤ n ≤ 100 · 1 ≤ target[i] ≤ n · target is strictly increasing.

From brute force to the pattern: This is already minimal; the only decision is when to stop.

Spot it: Stack simulation: every number read is pushed; numbers not in target are popped immediately. Stop after the last target value.

Why not another pattern? There's only one valid strategy; reading beyond target[-1] adds useless operations.

Approach:

1. want = set(target).
2. For x from 1 to target[-1]: Push; if x not wanted, Pop.

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        want = set(target)
        ops = []
        for x in range(1, target[-1] + 1):  # stop once the last target value is placed
            ops.append("Push")
            if x not in want:
                ops.append("Pop")  # not part of target: remove it at once
        return ops

What the code is doing, line by line:

1. Numbers arrive in increasing order, and so does target, so wanted numbers are already in the right order.
2. Unwanted numbers are pushed and popped to skip them.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Target is 1..k → only Push.
• Gaps in target.
• n larger than the last target value (stop early).

Complexity: O(target[-1]) time and space.

Problem: Evaluate an expression with +, −, parentheses, spaces and unary minus (no eval).

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 3 * 10⁵ · s consists of digits, '+', '-', '(', ')', and ' '. · s represents a valid expression. · '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid). · '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid). · There will be no two consecutive operators in the input. · Every number and running calculation will fit in a signed 32-bit integer.

From brute force to the pattern: Repeatedly evaluating the innermost brackets with string rewriting is O(n²); the stack is one pass.

Spot it: Without ×/÷, only signs matter. Keep a running result and the current sign. A parenthesis starts a fresh sub-result; save the outer state on a stack and combine when it closes.

Why not another pattern? Converting to postfix (shunting-yard) works but is longer; recursion works but the stack makes the state explicit.

Approach:

1. Digits build num.
2. On +/−: result += sign · num, reset num, set sign.
3. On (: push result and sign, reset both.
4. On ): finish the inner result, then result = pushed_result + pushed_sign · result.

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        result = 0
        num = 0
        sign = 1
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in "+-":
                result += sign * num  # finish the previous number
                num = 0
                sign = 1 if ch == "+" else -1
            elif ch == "(":
                stack.append(result)  # save the outer state
                stack.append(sign)
                result = 0
                sign = 1
            elif ch == ")":
                result += sign * num
                num = 0
                outer_sign = stack.pop()
                result = stack.pop() + outer_sign * result  # plug the bracket into the outer expression
        return result + sign * num

What the code is doing, line by line:

1. A unary minus like -(2+3) just sets sign = −1 before the bracket, which multiplies the whole bracket's value.
2. Each bracket level has its own running result; the stack remembers the levels outside it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Unary minus before a bracket.
• Nested brackets.
• Spaces everywhere.

Complexity: O(n) time, O(depth) space.

Problem: Score a balanced string: () is 1, AB is A + B, (A) is 2 · A.

Solve it on LeetCode ↗

Constraints: 2 ≤ s.length ≤ 50 · s consists of only '(' and ')'. · s is a balanced parentheses string.

From brute force to the pattern: Recursive splitting of substrings is O(n²); the stack is one pass. (A depth-counting trick even gets O(1) space.)

Spot it: Nested structure evaluated from the inside out → a stack holding the running score of each open level.

Why not another pattern? Recursing on substrings re-scans them; the stack does it in one pass.

Approach:

1. Start with [0] (the outer level).
2. (: push 0 (a new level).
3. ): pop v; add max(2 · v, 1) to the new top (() is 1, (A) is 2A).

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]  # score accumulated at each open depth
        for ch in s:
            if ch == "(":
                stack.append(0)  # start a new group
            else:
                inner = stack.pop()
                stack[-1] += max(2 * inner, 1)  # "()" scores 1, "(A)" doubles A
        return stack[0]

What the code is doing, line by line:

1. Each stack entry is the score of the group currently open at that depth.
2. Closing a group turns its inner score into the group's score and adds it to its parent (the A + B rule).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• () → 1.
• Deep nesting ((())) → 4.
• Side by side ()() → 2.

Complexity: O(n) time, O(depth) space.

Problem: Remove the minimum number of parentheses (letters stay) so the string becomes valid; return any valid result.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s[i] is either '(' , ')', or lowercase English letter.

From brute force to the pattern: Trying subsets of brackets to remove is exponential; one stack pass removes exactly the unmatched ones.

Spot it: Matching brackets → a stack. A ) with nothing open can never be matched, so drop it right away. Any ( still on the stack at the end never got closed, so drop those too. Everything else is kept, which is the minimum removal.

Why not another pattern? Trying removal subsets (as in Remove Invalid Parentheses) is exponential; here any one valid answer is enough, so a single pass works.

Approach:

1. Scan left to right with a stack of indices of unmatched (.
2. ) with an empty stack → mark its index for removal; otherwise pop.
3. After the scan, the indices left on the stack are unmatched (: remove them too.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        chars = list(s)
        stack = []  # indices of "(" waiting for a match
        for i, ch in enumerate(chars):
            if ch == "(":
                stack.append(i)
            elif ch == ")":
                if stack:
                    stack.pop()  # matched
                else:
                    chars[i] = ""  # nothing to close: remove it
        for i in stack:
            chars[i] = ""  # "(" that never closed
        return "".join(chars)

What the code is doing, line by line:

1. Every removed ) had no ( before it to pair with, so removing it is unavoidable.
2. Every removed ( had no ) after it, so it's unavoidable too; nothing else is removed.
3. Blanking characters in a list and joining once keeps it O(n).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Only ))) → "".
• Letters only (unchanged).
• Nested and adjacent groups.

Complexity: O(n) time and space.

Problem: Repeatedly remove k adjacent equal letters until no more removals are possible.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · 2 ≤ k ≤ 10⁴ · s only contains lowercase English letters.

From brute force to the pattern: Repeated scanning is quadratic; the run stack is linear.

Spot it: Removals can cascade (removing a run joins its neighbours), which a stack handles naturally: keep runs as (char, count).

Why not another pattern? Rescanning the string after each removal is O(n² / k).

Approach:

1. For each ch: if it matches the top run, increment; else push (ch, 1).
2. When the top count reaches k, pop it.
3. Rebuild the string from the stack.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # [char, run length]
        for ch in s:
            if stack and stack[-1][0] == ch:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()  # k in a row disappear
            else:
                stack.append([ch, 1])
        return "".join(ch * count for ch, count in stack)

What the code is doing, line by line:

1. After popping a run, the next character compares with the run below, so cascades happen automatically.
2. Each character is pushed and popped at most once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Cascading removals.
• No removals.
• k = 2 vs larger k.

Complexity: O(n) time and space.

Problem: Repeatedly remove the leftmost occurrence of part from s until none remain.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 1000 · 1 ≤ part.length ≤ 1000 · s and part consists of lowercase English letters.

From brute force to the pattern: Repeated find-and-remove restarts each time; the stack does one pass.

Spot it: Removing the leftmost occurrence and continuing is the same as scanning left to right with a stack and deleting part as soon as it appears at the top.

Why not another pattern? Calling replace/find in a loop restarts the scan every time.

Approach:

1. Append each character to out.
2. If out ends with part, delete those characters.

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        out = []
        L = len(part)
        for ch in s:
            out.append(ch)
            if len(out) >= L and "".join(out[-L:]) == part:
                del out[-L:]  # remove the occurrence just completed
        return "".join(out)

What the code is doing, line by line:

1. The first occurrence to complete while scanning is the leftmost one in the current string.
2. Deleting from the top lets earlier characters join with later ones, like the real process.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Nested occurrences (daabcbaabcbc).
• part longer than s.
• No occurrences.

Complexity: O(n · m) time, O(n) space (KMP states make it O(n + m)).

Problem: Apply the operations (append letter, delete last, duplicate, reverse) and return the final string.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 20 · s consists of only lowercase English letters and special characters *, #, and %.

From brute force to the pattern: This is the simulation.

Spot it: With |s| ≤ 20 the string stays small: a direct simulation, using a list as a stack (append and pop at the end).

Why not another pattern? Version II needs reverse reasoning because the result can reach 10¹⁵ characters; here it can't.

Approach:

1. Letter → append; * → pop if non-empty; # → res += res; % → res.reverse().

class Solution:
    def processStr(self, s: str) -> str:
        res = []
        for ch in s:
            if ch == "*":
                if res:
                    res.pop()  # delete the last character
            elif ch == "#":
                res += res  # duplicate
            elif ch == "%":
                res.reverse()
            else:
                res.append(ch)
        return "".join(res)

What the code is doing, line by line:

1. A list makes append and pop O(1).
2. Duplication can double the length at most 20 times: up to 2²⁰ characters, still fine.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• * on an empty result.
• Several # in a row.
• Reverse then delete.

Complexity: O(final length · |s|) time in the worst case.

Problem: Count the atoms in a chemical formula with nested parentheses and multipliers; return them sorted with counts.

Solve it on LeetCode ↗

Constraints: 1 ≤ formula.length ≤ 1000 · formula consists of English letters, digits, '(', and ')'. · formula is always valid.

From brute force to the pattern: Expanding the formula is exponential in nesting; stacked counters are near-linear.

Spot it: Nested groups → a stack of counters (hash maps). Closing a group multiplies its counts and adds them to the enclosing group.

Why not another pattern? Recursion works too; string expansion of multipliers explodes.

Approach:

1. Atom: an uppercase letter plus lowercase letters, then an optional number.
2. (: push a new counter. ) + number: pop, multiply, merge into the top.
3. Format sorted names with counts > 1.

from collections import Counter

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        stack = [Counter()]
        i, n = 0, len(formula)

        def read_number():
            nonlocal i
            start = i
            while i < n and formula[i].isdigit():
                i += 1
            return int(formula[start:i]) if i > start else 1

        while i < n:
            ch = formula[i]
            if ch == "(":
                stack.append(Counter())  # a new group starts
                i += 1
            elif ch == ")":
                i += 1
                mult = read_number()
                group = stack.pop()
                for atom, c in group.items():
                    stack[-1][atom] += c * mult  # multiply and fold into the enclosing group
            else:
                start = i
                i += 1
                while i < n and formula[i].islower():
                    i += 1
                atom = formula[start:i]
                stack[-1][atom] += read_number()
        counts = stack[0]
        return "".join(a + (str(counts[a]) if counts[a] > 1 else "") for a in sorted(counts))

What the code is doing, line by line:

1. Each counter holds the atoms of one open group.
2. A missing number means 1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Nested parentheses.
• Multi-letter atoms (Mg).
• No numbers.

Complexity: O(n · depth) time in the worst case, O(n) space.

Problem: Robots move left or right with health values; on collision the weaker is removed and the stronger loses 1 (equal: both removed). Return survivors' health in input order.

Solve it on LeetCode ↗

Constraints: 1 ≤ positions.length == healths.length == directions.length == n ≤ 10⁵ · 1 ≤ positions[i], healths[i] ≤ 10⁹ · directions[i] == 'L' or directions[i] == 'R' · All values in positions are distinct

From brute force to the pattern: Time-step simulation is slow; the stack resolves each collision once.

Spot it: Like Asteroid Collision: sort by position, and a left-mover meets the most recent right-movers first → a stack.

Why not another pattern? Simulating time steps is slow and positions can be far apart.

Approach:

1. Process robots by position; right-movers go on the stack.
2. A left-mover fights the stack top: the weaker dies, the stronger loses 1; equal → both die.
3. Collect survivors and output by original index.

class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        health = healths[:]
        stack = []  # indices of robots moving right
        for i in sorted(range(len(positions)), key=lambda i: positions[i]):
            if directions[i] == "R":
                stack.append(i)
                continue
            while stack and health[i] > 0:
                j = stack[-1]
                if health[j] < health[i]:
                    health[j] = 0  # right-mover dies
                    stack.pop()
                    health[i] -= 1
                elif health[j] > health[i]:
                    health[i] = 0  # left-mover dies
                    health[j] -= 1
                else:
                    health[i] = health[j] = 0  # both die
                    stack.pop()
        return [h for h in health if h > 0]  # original order

What the code is doing, line by line:

1. Robots facing the same way, or already past each other, never collide.
2. A strong left-mover can defeat several right-movers in a row, losing 1 health each time.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal health (both removed).
• All moving one way.
• A left-mover surviving several fights.

Complexity: O(n log n) time (sorting), O(n) space.

Problem: Same operations as version I, but the result can be 10¹⁵ long. Return the character at index k (or '.').

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of only lowercase English letters and special characters '*', '#', and '%'. · 0 ≤ k ≤ 10¹⁵ · The length of result after processing s will not exceed 10¹⁵.

From brute force to the pattern: Simulation needs up to 10¹⁵ characters; backward index mapping is O(|s|).

Spot it: Building the string is impossible. Record the length after each operation, then go backwards: each operation tells where index k came from (a duplicate maps k to k mod half, a reverse to len − 1 − k), until a letter operation produced it.

Why not another pattern? Simulation can need 10¹⁵ characters.

Approach:

1. lens[i] = length after operation i.
2. If k ≥ lens[-1], return '.'.
3. Backwards: letter → if k is the last index, return it; # → k %= previous length; % → k = previous length − 1 − k; * → unchanged.

class Solution:
    def processStr(self, s: str, k: int) -> str:
        lens = []
        length = 0
        for ch in s:
            if ch == "*":
                length = max(0, length - 1)
            elif ch == "#":
                length *= 2
            elif ch != "%":
                length += 1  # a letter
            lens.append(length)
        if k >= length:
            return "."
        for i in range(len(s) - 1, -1, -1):
            ch = s[i]
            before = lens[i - 1] if i else 0
            if ch == "#":
                k %= before  # the second half copies the first
            elif ch == "%":
                k = before - 1 - k  # undo the reverse
            elif ch != "*" and k == lens[i] - 1:
                return ch  # this letter is exactly position k
        return "."

What the code is doing, line by line:

1. Deleting the last character never moves the others, so * doesn't change k (which is inside the shorter string).
2. After #, index k in the doubled string is index k mod before in the original.
3. A letter appended at position lens[i] − 1 is the answer if k points there; otherwise it came from earlier.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k out of range → '.'.
• Many duplications.
• Reverse right after duplication.

Complexity: O(|s|) time and space.

Problem: Evaluate a Lisp-like expression with let, add, mult, integers and lexically scoped variables.

Solve it on LeetCode ↗

Constraints: 1 ≤ expression.length ≤ 2000 · There are no leading or trailing spaces in expression. · All tokens are separated by a single space in expression. · The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer. · The expression is guaranteed to be legal and evaluate to an integer.

From brute force to the pattern: String rewriting can't handle scopes; a recursive evaluator is the natural fit.

Spot it: Nested parentheses → evaluate recursively over tokens. Variable scoping is a stack of scopes (hash maps): let pushes a scope, assignments go into it, and lookups search from the innermost scope outwards.

Why not another pattern? Regex or string replacement can't handle shadowed variables and nesting correctly.

Approach:

1. Tokenise: (, ) and words.
2. evaluate(): a number or variable returns its value; ( reads the operator.
3. add/mult: evaluate two sub-expressions. let: push a scope; while the next token is a variable followed by an expression, assign; the last expression is the value; pop the scope.

class Solution:
    def evaluate(self, expression: str) -> int:
        tokens = expression.replace("(", " ( ").replace(")", " ) ").split()
        self.i = 0
        scopes = [{}]  # innermost scope last

        def lookup(name):
            for scope in reversed(scopes):
                if name in scope:
                    return scope[name]  # the nearest enclosing assignment

        def value():
            tok = tokens[self.i]
            self.i += 1
            if tok != "(":
                return lookup(tok) if tok[0].isalpha() else int(tok)
            op = tokens[self.i]
            self.i += 1
            if op in ("add", "mult"):
                a = value()
                b = value()
                result = a + b if op == "add" else a * b
            else:  # let
                scopes.append({})
                while True:
                    tok = tokens[self.i]
                    if tok == "(" or not tok[0].isalpha() or tokens[self.i + 1] == ")":
                        result = value()  # the final expression
                        break
                    self.i += 1
                    scopes[-1][tok] = value()  # assign in this scope
                scopes.pop()
            self.i += 1  # skip ")"
            return result

        return value()

What the code is doing, line by line:

1. A let body is "variable value" pairs until a token that's an expression on its own: a (, a number, or a variable right before ).
2. Assignments go into the innermost scope, so shadowing works and disappears when the let ends.
3. Each token is consumed once, so evaluation is linear.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Shadowed variables.
• Reassigning in the same let (let x 3 x 2 x).
• Negative numbers.

Complexity: O(n · depth) time (scope lookups), O(n) space.