Where it runs
1. The problem
Look at a line of code with brackets inside brackets: foo([a, {b: 1}]). Every ( needs a ), every [ needs a ], every { needs a }. And they must close in the right order. If you open a square bracket and then a curly one, the curly one must close first. Get it wrong, and your editor marks the spot at once.
Now do that check yourself, in code, over a whole line. The hard part is the order. In ([)] the count is right: two opening brackets and two closing ones. But the nesting is wrong: ) tries to close while [ is still open. You need to catch that.
The first idea is to count. Add 1 for each opening bracket, subtract 1 for each closing one, and check that the total ends at 0. On ([)] this check gets it wrong: the total ends at 0, and the string is called correct. A counter knows how many brackets are open, but it does not remember which ones.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedisValid("([]{()})")Check that every bracket is closed in the right order. An opener goes on the stack. A closer must match the top.
Recognise it
Say these words and it is this pattern
- valid parentheses / balanced brackets
- match the most recent open with the next close
- undo, backtrack to the last state, nested structure
- evaluate an expression with nested operators
- process in reverse order of arrival
Looks similar, isn't
- Monotonic stack
That keeps the stack ordered so every pop answers a question. A plain stack only remembers what is open.
- Recursion
Every recursive call already sits on a stack. Writing your own avoids the depth limit.
- Graph BFS / DFS
A queue gives breadth-first order, a stack gives depth-first. Same traversal, different container.
- Monotonic deque (sliding window max/min)
A deque can be read and trimmed at both ends. A stack only ever touches the top.
Every push and pop is O(1), so n operations cost O(n). Memory is O(n) in the worst case.
On LeetCode
Problems on brackets and nesting, where the last thing opened must close first. Push each opener, and on each closer pop and check that it matches.
The lesson task with only bracket characters in the string.
Push the index of each opener, pop on a matching closer, and delete the closers with nothing to match plus the openers left on the stack.
On each opening bracket push the repeat count and the text built so far, and on the closing one pop them and repeat.
Push indices instead of characters, so the distance to the new top after a pop is the length of a valid run.