DSA Tracker

Visualize

Stack matching

A stack remembers openers in last-in-first-out order, so the top is always the newest bracket still waiting to close. Reach for it whenever the most recent unfinished thing must finish first — matching brackets, undo, nested calls.

Details

Animated on: Valid Parentheses on "({[]})"

Problem:Valid ParenthesesEasy

Stack

step 1 / 11

(
[0]
{
[1]
[
[2]
]
[3]
}
[4]
)
[5]

Input "({[]})". Valid means every closer matches the newest unclosed opener. A stack tracks exactly that. Stack: empty.

  • i=0· arr[0] = (
Pseudocode
1FUNCTION isValid(s):
2  make an empty stack
3  FOR each position i from 0 to the length of s:
4    ch = s[i]
5    IF ch is an opener '(' or '{' or '[':
6      push ch onto the stack
7    ELSE IF popping the top does not equal the matching opener of ch:
8      RETURN false
9    END IF
10  END FOR
11  RETURN whether the stack is now empty
12END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Input "({[]})". Valid means every closer matches the newest unclosed opener. A stack tracks exactly that. Stack: empty.
  2. '(' is an opener — nothing to match yet, so remember it: push. Stack: (
  3. '{' also opens. Push on top — the newest opener must be the first to close. Stack: ( {
  4. '[' opens too. Push. Three openers now wait, '[' on top. Stack: ( { [
  5. ']' is a closer. It can only pair with the newest open bracket — whatever sits on top of the stack.
  6. Pop the top: '['. It matches ']' — pair closed, both retire. Stack: ( {
  7. '}' closes next. Top of stack is '{' — the newest bracket still open — so that's who it must match.
  8. Pop '{' — matches '}'. The nesting is unwinding in perfect reverse order. Stack: (
  9. Last char ')' — a closer. Only '(' remains on the stack, pushed first, closing last.
  10. Pop '(' — matches ')'. Every opener found its closer. Stack: empty.
  11. Loop done, stack empty — no opener left hanging. Return true: "({[]})" is valid.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Valid Parentheses in the editorAll Stack problemsBack to roadmap