Balanced Brackets Question

At some point in time balanced brackets question will be asked as a technical clearance.

First glance it seems very difficult problem and yes it is. With little understanding of stacks we can solve it with little code.

Lets understand what is Balanced Brackets Problem

  1. We will be given list of accepted brackets.
  2. Input will be rendomly constucted string out of those acceptsd bracket list.
  3. Now we need to check if this string is balanced with list of accepted brackets.
  4. if its balanced return true if not return false

Let's understand term balanced breackets

  • Balanced breackets means each bracket must have its opening and closing pair. for ex: if we take round bracket then there must be opening and closing round bracket in string to make it pair.

  • Next this pair must be excatly placed in such way that other opening and closing pair must match.

  • Each pair either contain no pair inside of them or only contain matching pair inside them.

  • if you satify these rules then only string can be called as Balanced Brackets string

Lets check some example of valid and invalid Balanced Brackets

1. () 
// this is valid pair

2. {()}
// this is again valid pair as 
// 1. () round braces contains no pair inside and they are complete open and close
// 2. {} curly braces contains other braces but they are also a valid pair 

// so final string is valid Balanced Brackets string

3. {([)]}
// this is invalid pair
// 1. you can directly point out [ ] square braces do not follow rules 
// 2. [ ] square brances are not conataing valid pair as it has single ( round bracket
// 3. same goes for ( ) round brances they contain invalid single [ square bracket

// so final string is not Balanced Brackets string

// ======================
// some other examples
// ======================

4. [{()[]}] // this is valid 
5. [{()[<>]}] // this is valid 

6. [{()[<]}] // this is NOT valid
7. [{()[<}] // this is NOT valid 

Now you all get better idea what we are dealing with so, we can move to solution how to validate Balanced Brackets string programatically.

Balanced Brackets Solution

Lets directly introduce you with the code snippet of it then we can understand it

Balanced Brackets Code

let isBracketsBalanced = (input) => {

  let availableBrackets = "[]{}()<>";
  let stack = [];

  for(let bracket of input) {
    let indexOfBracket = availableBrackets.indexOf(bracket);

    if(indexOfBracket % 2 === 0) {
      stack.push(indexOfBracket + 1);
    } else {
      if(stack.pop() !== indexOfBracket) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

Reference: Solving Balanced Brackets in Javascript with Stacks

Let's briefly understand this logic.

At first glance it looks like it is trying to match starting and closing brackets.

But its more than that it is using stack to store(push) previous bracket values and fetch(pop) values for comparison.

Lets understand code step by step:

  1. let availableBrackets = "[]{}()<>";

    It is defining avaialble brackets which we need to check inside string. we need to specify which brackets we are going to check for pairing.

  2. let stack = [];

    It is defining array(stack) to store(push) and retrive(pop) brackets to keep track of pairs.

  3. for(let bracket of input) { /*code*/ }

    for loop which will iterate through each character of input string and execute block of code for that given charater.

  4. let indexOfBracket = availableBrackets.indexOf(bracket);

    It will get the index of bracket from availableBrackets

  5. if(indexOfBracket % 2 === 0) { /*code*/ } else { /*code*/ }

    This condition is checking that given bracket index is for closign bracket or starting bracket

    • indexOfBracket % 2 === 0 If it is true that means its starting bracket
    • indexOfBracket % 2 === 0 If it is false that means its ending bracket
    • availableBrackets string arranged in such way that charter start from 0 is starting bracket and each odd numbered index is closing bracket and each even numbered index is starting bracket
    • Now, indexOfBracket % 2 === 0 will be always true for starting bracket. clever arrangement !
  6. stack.push(indexOfBracket + 1);

    If given bracket from loop is starting bracket it will push in stack with (index number of bracket + 1) means we are actually storing index of closing bracket in stack.

  7. Now If we are in else part means given bracket is not starting so its ending bracket

    • if(stack.pop() !== indexOfBracket) {
          return false;
      }
    • HERE is the main logic of this code comes in to play
    • Now we know its ending bracket so we try to retrive lastly PUSHED value from our stack and compare it with the given bracket if both are matched ALL GOOD
    • If they do not match then we have problem as pair of starting and ending bracket is not MATCHED and it will return FALSE - means our input string is not BALANCED BRACKETS.
  8. Further more suppose we did not encounter any problem during loop at the end of the logic stack will have ZERO element in it as we push and pop equal number of the bracket from it. so we can return TRUE and our input string is a BALANCED BRACKETS.

  9. If somehow stack has non zero length then it means any bracket is missing there closing bracket and was not able to POP all the elements in this scenario stack length will be NON ZERO and it wil return FALSE and our input string is not BALANCED BRACKETS.

I hope this explanation will help you understand Balanced Breackets problem. I hope you can able to answer it with confidence in your next interview questions.

js interview questions