Valid Brackets Coding Interview Question |
Interview Question

Valid Brackets

Course launching November 17, 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.