Stack: definition
A stack stores items in last-in, first-out order (LIFO). Push adds an item to the top; pop removes the top item. Use a stack when the most recent unfinished item must be handled first.
Problems this pattern can solve
- Match nested brackets
- Evaluate postfix expressions
- Track undo actions
- Find the next greater value with a monotonic stack
Task example: Valid Parentheses
Given a string containing only ()[]{}, decide whether the brackets form complete, correctly nested pairs. Each closer must match the most recent unmatched opener. Return True only if no bracket is left unmatched.
s = "([])" → True
s = "([)]" → False
s = "(" → FalseThe square pair closes inside the round pair. In ([)], the round closer arrives while a square opener is still waiting, so the pairs cross and the result is False.
Source task: LeetCode 20Repeated pair removal: video explanation
s = "([])" → True
Prefer reading? Follow the steps below.
- Save the previous string, then remove adjacent (), [], and {} pairs. Each replace call removes all non-overlapping occurrences of that pair.
- Repeat until a full pass leaves the string unchanged. Removing an inner pair can expose another pair for the next pass: ([]) becomes (), then empty.
- Return True if the final string is empty; otherwise return False. Every nonempty valid sequence has an adjacent matching pair, and deleting one preserves validity.
Time complexity · O(n²)
With n brackets, deeply nested input can require O(n) passes, each scanning O(n) characters. Worst-case time complexity is O(n²).
Space complexity · O(n)
Python strings are immutable. The previous string and replacement results occupy O(n) peak extra space; old temporary strings do not all stay in memory.
Stack: video explanation
s = "([])" → True
Prefer reading? Follow the steps below.
- Read left to right. Push every opening bracket onto the stack. Its top is the most recent unmatched opener.
- For a closer, return False if the stack is empty. Otherwise pop the top and compare it with the opener required by that closer. A mismatch returns False immediately.
- After the scan, return not stack. An empty stack means all pairs closed; leftover openers mean False. Never search deeper for a matching opener: that would permit crossing pairs.
A stack avoids repeated scans by storing exactly the unmatched openers. Compared with pair removal, worst-case time improves from O(n²) to O(n). Worst-case extra space stays O(n).
Time complexity · O(n)
Each character is read once. Each opener is pushed once and popped at most once. Python list append and pop from the end take amortized O(1) time, giving O(n) total time.
Space complexity · O(n)
The stack can hold n openers in the worst case. The bracket mapping has constant size, so extra space is O(n).