Valid Parentheses

Start dumb: cancel pairs until nothing moves

The hands-on first idea: repeatedly delete every adjacent matched pair — (), [], {} — until the string stops changing; valid means nothing is left. It works, but each sweep is O(n) and can remove as little as one pair, so the whole thing is O(n²) with string rebuilding on every pass.

Find the bottleneck

All that rescanning is searching for something the scan already walked past: the most recently opened bracket. Brackets nest like function calls — last opened, first closed. The rescan re-discovers, over and over, a fact the algorithm could simply have remembered.

The optimal shape

One pass, one stack:

1. Opener → push it; nothing about it can be decided yet.
2. Closer → pop the top; if the types disagree (or the stack was empty), return false on the spot — no future character can fix it.
3. After the scan, the stack must be empty: unclosed openers are as invalid as mismatched closers.

Each character is pushed and popped at most once — O(n) time, O(n) stack space in the worst case ((((((). In the player, the brackets still on the stack stay highlighted as the open “window”; matched pairs retire to green.

Watch it think

Run the default, then the traps: the empty string (vacuously true), a lone ) (closer with nothing open), ((( (the leftover-openers bug), and ([)] (right types, wrong nesting).

1fun isValid(s: String): Boolean {
2    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
3    val stack = ArrayDeque<Char>()
4    for (c in s) {
5        if (c in pairs) {
6            if (stack.removeLastOrNull() != pairs[c]) return false
7        } else {
8            stack.addLast(c)
9        }
10    }
11    return stack.isEmpty()
12}