Skip to main content
DSA patterns

Valid Parentheses

easyStack and queue Must-doeBay Cloud SREIntuit Senior SREAmazon SDEServiceNow Senior Software Engineer

Problem statement

You are given a string s that contains only the six characters (, ), [, ], { and }. Return true if the brackets are balanced, and false if they are not.

The brackets are balanced when two rules hold:

  1. Every opening bracket is closed by the same kind of bracket. ( must be closed by ), not by ].
  2. Brackets close in the right order. The bracket opened most recently must be the first one closed.

Think of a quick check on a config file or a template before you deploy it: every { and [ has to be closed properly, or the file will not parse.

Examples

Example 1

Input: s = "()"

Output: true

Explanation: The ( is closed right away by a ) of the same kind.

Example 2

Input: s = "()[]{}"

Output: true

Explanation: Three pairs, one after another. Each pair opens and closes before the next one starts.

Example 3

Input: s = "(]"

Output: false

Explanation: The ( is closed by a ], which is a different kind of bracket.

Hints

Hint 1: Look at ([)]. Every bracket has a partner of the right kind, yet the string is not valid. Think about what is wrong with the order.

Approach

Optimal: Stack

Intuition

A stack is a pile where you can only add to the top and take from the top. The last item you put on is the first one you take off.

That is exactly how brackets behave. The bracket opened last is the one that must be closed first. So we walk through the string and keep a pile of "opened but not yet closed" brackets.

  • When we see an opening bracket, we put it on the pile.
  • When we see a closing bracket, it must match the bracket on top of the pile. If it does, we take that bracket off. If it does not match, or the pile is empty, the string cannot be valid.

At the end the pile must be empty. A leftover bracket means something was opened and never closed.

This is faster than removing pairs because we never rescan the string. Each character is handled once.

Steps

  1. Make a lookup that maps each closing bracket to its opening partner: ) to (, ] to [, } to {.
  2. Start with an empty stack.
  3. For each character ch in the string:
    • If ch is a closing bracket: if the stack is empty, or the top is not its partner, return false. Otherwise pop the top.
    • If ch is an opening bracket: push it.
  4. After the loop, return true only if the stack is empty.

Dry run

s = "([])"

step ch action stack after
1 ( opening, push (
2 [ opening, push ( [
3 ] top is [, matches, pop (
4 ) top is (, matches, pop empty

The stack is empty at the end, so the answer is true.

Now s = "(]". Step 1 pushes (. Step 2 sees ], but the top is (, which is not its partner, so we return false straight away.

Edge cases: an empty string returns true because the stack is empty. A string that starts with a closing bracket, like ")", hits an empty stack, so it returns false. A string like "((" ends with a non-empty stack, so it returns false.

Complexity

Time O(n) - We look at each character exactly once. Pushing onto a stack and popping from it each take constant time. So the whole pass costs O(n), and the worst case is the same as the average case.

Space O(n) - The stack holds opening brackets that are still waiting for a partner. In the worst case, such as `"((((("`, every character is an opening bracket and all of them sit on the stack. We do not count the input string itself.

class Solution:
    def isValid(self, s: str) -> bool:
        match = {")": "(", "]": "[", "}": "{"}
        stack = []
        for ch in s:
            if ch in match:
                if not stack or stack.pop() != match[ch]:
                    return False
            else:
                stack.append(ch)
        return not stack


if __name__ == "__main__":
    print(str(Solution().isValid("()")).lower())  # true
    print(str(Solution().isValid("()[]{}")).lower())  # true
    print(str(Solution().isValid("(]")).lower())  # false
RecapThe whole problem in a few lines, for the night before
  • Spot it: brackets or tags that must open and close in the right order
  • Idea: push each opening bracket; for a closing one, the top of the stack must be its partner, then pop
  • Cost: O(n) time, O(n) space
  • Trap: popping an empty stack on input like ")"; also the stack must be empty at the end, or "((" passes wrongly

Interview follow-ups

  • The string has only one kind of bracket, ( and ). Can you use less memory?

    Yes. With one kind of bracket you do not need to remember which one is on top, only how many are open. Keep a counter: add 1 for ( and subtract 1 for ). If the counter ever goes below zero, return false, because a ) had no partner. At the end the counter must be 0. This is still O(n) time but only O(1) space.

  • Return the position of the first bracket that breaks the rule, not just true or false.

    Push the index of each opening bracket instead of the bracket itself, so you know where it was. When a closing bracket does not match, or the stack is empty, that closing bracket's index is the first error. If the loop ends with a non-empty stack, the first error is the unmatched opener at the bottom of the stack. Time and space stay O(n). This is how a real linter points at the exact line.

Frequently asked questions

Brackets must close in the reverse order they opened. That "last in, first out" rule is exactly what a stack gives you. The top of the stack is always the bracket that must be closed next. Any other structure, like a plain counter, forgets which bracket came last.

A string like ")" starts with a closing bracket and nothing was opened yet. If you pop from an empty stack, Python raises an error and Java throws an exception. Checking first turns that case into a clean false. This is the most common bug in this problem.

No. Counting only checks that the numbers match, not the order or the kind. The string "([)]" has one of every bracket, so the counts match, yet it is invalid because the ) arrives while [ is still open. The stack catches this because the top is [ when ) shows up.

Yes. A valid string always has an even length, because brackets come in pairs. If the length is odd you can return false at once. It saves time on some inputs but does not change the O(n) cost.

Configs and templates are full of nested brackets: JSON, YAML flow style, Terraform blocks, shell ${...} expansions and Jinja {{ ... }}. A linter or a pre-commit hook checks that brackets balance before the real parser runs. The same stack idea sits inside every parser, so interviewers use this as a warm-up for harder parsing questions.