Stack: Valid Parentheses

A stack remembers what is still open, and the most recent one must close first.

The idea

A stack is like a pile of plates: you can only add to the top and only take from the top (last in, first out). To check brackets, walk through the text. Each opening bracket goes on the pile. Each closing bracket must match the plate on top, and then that plate is removed. If the closer does not match (or the pile is empty), the text is invalid. At the end the pile must be empty.

Watch it work

Try it

Common mistakes

How fast is it?

Time: O(n) – each character is pushed or popped once. Space: O(n) in the worst case (all opening brackets).