Valid Brackets Coding Interview Question |
Interview Question

Valid Brackets

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

Given an input string that contains brackets, write a function hasValidBrackets that returns a boolean indicating whether the brackets are valid.

  • The brackets we will consider are (, ), [, ], {, }.
  • The string can contain other characters, but those can be ignored.
  • A string is valid if there are an equal number of opening bracks and closing brackets of the same type with all being matched.
  • Brackets are considered matched if they appear in the correct order (must be opened before they are close) and don't overlap.
() // true
][ // false
{}[]() // true
{[]} // true
([) // false
{(}) // false
{[(([{}]))]} // true
{[]{()}} // true

Validate My Answer

  1. Every opening bracket must have a closing bracket AND they must be ordered correctly to be valid.

  2. Think about solving this from the inside-out. For the brackets to be valid, you can start with the innermost open/close pair and compare those. If those match, you would set them aside and check the pairs after it. You really just need to be validating one potential match at a time.

  3. With an additional data structure, you can solve this in O(n) time and space and only iterate through the string once.