Easy · Stack
Understand → Visualise → Practice.
Brackets close in the reverse order they open. Last in, first out is exactly what a stack gives you.
Push every opening bracket. Each closing bracket must match the bracket on top of the stack.
(, [ and { go on the stack.
Pop and compare; a mismatch or empty stack fails.
Leftover openers mean the string is invalid.
O(n) time, O(n) space in the worst case.
Don't forget the final check: "((" never fails a match, but it is still invalid.
Read the full guides first: Stacks, Queues and Deques.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.