LeetCode 20 Valid Parentheses - Example and Complexity Analysis

Trace "{[()]}".

Read {: push. Stack: [{].

Read [: push. Stack: [{, [].

Read (: push. Stack: [{, [, (].

Read ): top is (, matches. Pop. Stack: [{, [].

Read ]: top is [, matches. Pop. Stack: [{].

Read }: top is {, matches. Pop. Stack: [].

Stack empty at end. Return true.

For "([)]": after ([, when you see ), top is [ which doesn't match. Return false.

Single pass through the string. $O(n)$ time. Stack holds at most $n$ characters. $O(n)$ space.