Valid Parentheses — Complete Problem Walkthrough

If you have ever wondered why stacks exist as a data structure, Valid Parentheses (#20) is the answer. This LeetCode easy is the simplest, most elegant demonstration of the Last-In-First-Out principle, and it is almost certainly the first problem most engineers solve with a stack.

The valid parentheses leetcode problem has over 20 million submissions, making it one of the most attempted problems on the platform. There is a reason for that — it is the gateway to an entire category of stack-based interview questions that appear at every major tech company.

In this walkthrough, you will learn exactly how the bracket matching algorithm works, why a stack is the perfect tool for the job, and how this single pattern extends to harder problems like Decode String (#394) and Daily Temperatures (#739).

Given a string containing just the characters (, ), {, }, [, and ], determine if the input string is valid. A string is valid when every opening bracket has a corresponding closing bracket of the same type, and brackets close in the correct order.

For example, "({[]})" is valid because each opening bracket is matched by its correct closing bracket in the right nesting order. But "([)]" is invalid — even though every bracket has a partner, they overlap instead of nesting properly.

This distinction between overlapping and nesting is exactly what makes the problem interesting. You cannot solve it by simply counting brackets. The order matters, and that is where the stack comes in.

A stack is a Last-In-First-Out (LIFO) data structure — the last item you push onto it is the first one you pop off. This property maps perfectly to nested brackets because the most recently opened bracket must be the first one closed.

When you encounter an opening bracket, you push it onto the stack. When you encounter a closing bracket, you pop the top of the stack and check if it matches. If the brackets are properly nested, the most recent open bracket will always correspond to the current closing bracket.

The stack naturally tracks the nesting depth. At any point during traversal, the stack contains all the currently open brackets that have not yet been closed, with the innermost bracket on top. When you finish scanning the string, the stack should be empty — every opener found its closer.

This is the core insight behind the valid parentheses stack solution: LIFO order mirrors nesting order. No other data structure captures this relationship as cleanly.

The leetcode 20 solution uses two components: a stack to track open brackets, and a hash map that maps each closing bracket to its corresponding opening bracket. This combination produces clean, extensible code with no if-else chains.

Here is the approach in plain English. Initialize an empty stack and a mapping of closing-to-opening brackets: ) maps to (, ] maps to [, and } maps to {. Then iterate through each character in the string.

For each character, check if it is a closing bracket by looking it up in the map. If it is not in the map, it must be an opening bracket — push it onto the stack. If it is a closing bracket, pop the top of the stack and verify it matches the expected opening bracket from the map. If the stack is empty when you need to pop, or the popped bracket does not match, return false immediately.

After processing every character, return true only if the stack is empty. A non-empty stack means there are unmatched opening brackets remaining.

Let us trace through "({[]})" to see the stack in action. Start with an empty stack: []. Read "(" — it is an opener, push it. Stack: ["("]. Read "{" — opener, push it. Stack: ["(", "{"]. Read "[" — opener, push it. Stack: ["(", "{", "["].

Now read "]" — it is a closer. Pop the stack: we get "[". The map says "]" should match "[". It matches, so we continue. Stack: ["(", "{"]. Read "}" — closer. Pop: we get "{". The map says "}" matches "{". Correct. Stack: ["("]. Read ")" — closer. Pop: we get "(". The map says ")" matches "(". Correct. Stack: [].

The stack is empty after processing all characters, so "({[]})" is valid. Every bracket found its match in the correct nesting order.

Now trace "([)]" — the classic invalid case. Stack starts empty. Push "(". Stack: ["("]. Push "[". Stack: ["(", "["]. Read ")" — closer. Pop: we get "[". But the map says ")" should match "(", not "[". Mismatch detected — return false immediately.

This is why counting alone fails. "([)]" has equal counts of every bracket type, but the nesting order is wrong. The stack catches this because LIFO order enforces proper nesting. The time complexity is O(n) since we visit each character once, and space complexity is O(n) for the stack in the worst case.

Edge cases reveal whether you truly understand the problem. Interviewers pay close attention to how you handle boundary conditions, and the balanced parentheses problem has several worth discussing upfront.

The empty string is considered valid — there are no brackets to mismatch. A string with odd length is guaranteed invalid because every bracket needs a partner, and an odd number of characters means at least one bracket is unmatched. Checking for odd length first is a quick O(1) early return.

A string containing only opening brackets like "(((" is invalid because the stack will never empty. Conversely, a string with only closing brackets like ")))" fails on the first character because the stack is empty when you try to pop. A single character is always invalid since it cannot form a complete pair.

Valid Parentheses is not just a warm-up problem — it introduces the fundamental pattern behind an entire family of stack questions. The core insight is that a stack matches LIFO order to nested structure. Any time a problem involves matching, nesting, or tracking the most recent unresolved item, a stack is likely the right tool.

This same pattern appears in Min Stack (#155), where you track the current minimum alongside the main stack. It shows up in Decode String (#394), where nested encoded strings like "3[a2[c]]" require you to push and pop partial results. Daily Temperatures (#739) uses a monotonic stack variant where you find the next warmer day by maintaining a stack of indices.

The bracket matching algorithm is your entry point into all of these problems. Once you internalize push-on-open and pop-on-close, the harder variants become natural extensions rather than new concepts. Practice recognizing when LIFO order solves the problem, and review with YeetCode flashcards to lock in the pattern before your next interview.