Black Friday 50% off any plan, for life Ends Nov 30

Coding interview problems

Valid Parentheses

Valid Parentheses looks like a counting problem. Count, and ([)] passes when it should fail. The interviewer wants to see you reach for a stack and catch every way a string can fail.

Don't miss an edge case in the room

A stack makes sense once you've seen it. Make sure you don't blank on an edge case in the room: write it yourself in the 14-day free trial, and the learning engine brings it back before you forget it.

14-day free trial. Cancel anytime with one click.

I have an account

The problem

Given a string containing only the characters (, ), {, }, [ and ], return true if the string is valid and false if it is not.

The string is valid when:

  • Every opening bracket is closed by a bracket of the same type.
  • Opening brackets are closed in the correct order: the most recent bracket still open is the first one to be closed, so ([)] is not valid.
  • Every closing bracket has an opening bracket of the same type before it.

Constraints

  • 1 <= length of the string <= 10^4
  • The string contains only the characters ()[]{}.

Example

Input
s = "{[(])}"
Output
false

Every bracket has a partner of its own kind, but the square pair and the round pair overlap: ] arrives while ( is still open.

  1. 0:00Valid Parentheses
  2. 0:40The problem
  3. 1:08Why not count?
  4. 1:44The rules
  5. 2:13Walkthrough
  6. 2:49Three ways to fail
  7. 3:18Complexity
  8. 3:30Code
  9. 4:08Follow-up: one kind
  10. 4:45Recap

How to solve it

Counting doesn't work. {[(])} has one bracket of each kind opened and closed, and it's still invalid. Counts know how many brackets are open, not which one opened last, and the last one opened has to close first. That is last in, first out: a stack.

So read the string once. For each opening bracket, push the closing bracket it needs. For each closing bracket, pop the top of the stack: if the stack was empty, or the popped bracket isn't this one, return false. At the end, the string is valid only if the stack is empty.

Valid Parentheses({[(])})

The run starts on "{[(])}".

Those checks are the three ways a string fails: a closer with nothing open, a closer that doesn't match the top, and openers left over at the end. The first two fail inside the loop; the last is the empty check after it. Name all three before you code.

The follow-up: what if there's only one kind of bracket? Then any closer can close any opener, so a counter is enough. Add one for (, subtract one for ), return false if it ever drops below zero, and check that it ends at zero. That's O(1) space.

Python solution

class Solution:
    def check_valid(self, s: str) -> bool:
        open_close_pairs = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        stack = []
        for c in s:
            if c in open_close_pairs:
                stack.append(open_close_pairs[c])
            elif len(stack) == 0 or stack.pop() != c:
                return False
        return len(stack) == 0

Time and space complexity

Time O(n)
Each character is read once, and every push and pop is constant time.
Space O(n)
A string of only opening brackets fills the stack.

Be ready for the next one

Walk into the coding round ready

Practice 1,500+ real interview questions, built by former Meta, X and LinkedIn engineers. 50,000+ engineers have prepared with Firecode.

14-day free trial. Cancel anytime with one click.

Built by former engineers at

I have an account
50,000+engineers preparing with Firecode
1500+real interview questions from top tech companies
14languages, from Python to Rust
FAANG+offers landed at Google, Meta, Netflix, and more
Google Meta Amazon Apple Microsoft Netflix OpenAI Anthropic Stripe Nvidia Airbnb Uber Coinbase DoorDash Spotify Shopify Snowflake Cloudflare Bloomberg Dropbox