Valid Parentheses

Table of Contents +

This one looks simple. But it hides a lot. The interviewer hands you a string of brackets and asks “are these balanced?”. What they really want to see is whether you reach for the right tool. So the trick here is spotting that a stack fits this problem perfectly. A stack is a list where the last thing you put in is the first thing you take out. Once you see that, the rest is easy.

🧩 The Problem

You get a string that has only these characters: (, ), [, ], {, and }. You have to tell if the brackets are balanced. Balanced means every opening bracket has a matching closing bracket of the same type. And they must close in the right order.

So ()[] is fine. But (] is not. A round bracket cannot be closed by a square one. And ([)] is not fine either, because the order is wrong. The inner bracket must close before the outer one.

Input:  "([]{})"
Output: true


Input:  "([)]"
Output: false

🐌 The Simple Idea First

A first thought many people have is to keep removing matching pairs. So you scan the string. You find a () or [] or {} sitting next to each other. You delete it. Then you scan again. You repeat until nothing is left, or nothing can be removed.

This works, but it is slow. Every time you delete a pair you start scanning from the beginning again. For a long string that means doing the same work again and again. So the time cost grows fast, close to O(n²). In an interview that answer is okay to mention. But they want better.

📚 The Stack Approach

Here is the clean way. Think about what “correct order” really means. The bracket you opened most recently is the one that must close first. See that pattern? Last in, first out. That is exactly what a stack gives you.

So you walk through the string one character at a time:

  • If it is an opening bracket, push it on the stack.
  • If it is a closing bracket, pop the top of the stack and check it. The popped item must be the matching opening bracket. If the stack was already empty, or the popped item does not match, the string is invalid.

When you finish the whole string, the stack must be empty. If something is still sitting there, it means an opening bracket never got closed. So that string is invalid too.

Note

Two checks can fail a string mid-way: a closing bracket when the stack is empty (nothing to match it), or a closing bracket where the popped item does not match. And one check fails at the end: leftover items on the stack.

Steps to solve it

  1. Make an empty stack and a small map that links each closing bracket to its opening bracket.
  2. Go through each character in the string.
  3. If it is an opening bracket, push it onto the stack.
  4. If it is a closing bracket, pop the top of the stack and check it is the matching opening bracket. If the stack was empty, or it does not match, return false.
  5. After the loop ends, return true only if the stack is empty.

This Python version uses a list as the stack and a dictionary to link each closing bracket to its opening one.

valid_parentheses.py
def is_valid(s):
    # map each closing bracket to its opening bracket
    match = {')': '(', ']': '[', '}': '{'}
    stack = []


    for c in s:
        if c in '([{':
            stack.append(c)              # push opening bracket
        else:
            # stack empty, or popped top does not match
            if not stack or stack.pop() != match[c]:
                return False
    return len(stack) == 0               # valid only if stack is empty




print(is_valid("([]{})"))
print(is_valid("([)]"))

The output of the above code will be:

True
False

⏱️ Time and Space Complexity

The stack way looks at each character one time. So the time grows in a straight line with the length of the string. That gives us O(n) time. The space depends on how many opening brackets pile up before they close.

Approach Time Space
Remove matching pairs again and again O(n²) O(n)
Stack (optimal) O(n) O(n)

Tip

A neat point to say out loud in the interview: if the string has an odd number of characters, it can never be balanced. So you can return false right away without using the stack at all. Small touches like this show the interviewer you are thinking.

🧩 Key Takeaways

  • ✅ Brackets must close in the reverse order they open. That last-in, first-out pattern is why a stack is the right tool.
  • ✅ Push every opening bracket. On each closing bracket, pop the top and check it is the matching opening bracket.
  • ✅ A closing bracket with an empty stack means invalid. Leftover items at the end also mean invalid.
  • ✅ One clean pass gives you O(n) time and O(n) space.
  • ✅ An odd-length string can never be balanced, so you can reject it early.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why is a stack the right data structure for this problem?

    Why: Correct nesting means the last opened bracket closes first, which is exactly the last-in, first-out behaviour of a stack.

  2. 2

    While scanning, you hit a closing bracket but the stack is empty. What does this mean?

    Why: A closing bracket with nothing on the stack has no opening bracket to match, so the string is invalid.

  3. 3

    After scanning the whole string, the stack still has items in it. What is the result?

    Why: Leftover items mean opening brackets that never got a matching close, so the string is invalid.

  4. 4

    What is the time complexity of the stack solution?

    Why: Each character is looked at exactly once and each stack push or pop is constant time, so the total work is O(n).

Score: 0 / 4

🚀 What’s Next?

Previous Remove the Nth Node from the End Next Next Greater Element

Share & Connect

Share on LinkedIn