Brace yourself - code kata solution

The IT market where I live is currently pretty bad for juniors and early mid developers. To get an interesting position you first need to be the lucky one that gets to technical interview. And when you get the chance you want to be ready.

So I keep myself busy by learning a lot of theory required for many of these positions like microservices and cloud architecture, design patterns and so on.

I recently went through a challenging technical interview. After an hour and a half of all the usual “how js and node works” and a lot of serverless architecture questions I got to the live coding part. The task was rather simple but I think I could do a better job in finishing it faster. So I decided to practice solving these code puzzles on a more regular basis.

In this post I want to show you my approach to solving “Valid braces” kata from Codewars. The task was actually sent to me by a dear friend of mine and the message following the link read “This will b**w your mind”.

The Problem

The Puzzle is called "Valid Braces".

You are given a string of different types of braces “{[(“.

Your task is to write a function that validates if each brace has a corresponding pair similar to how your IDE would suggest a missing brace closing.

Example outputs would look like this:

// "(){}[]"   =>  True
// "([{}])"   =>  True
// "(}"       =>  False
// "[(])"     =>  False
// "[({})](]" =>  False

The solution requires making use of a stack - a data structure that takes an element that was added last if condition is met. Similarly to a list of orders are put to a stack of cards.

We will also need a map of braces. We can either use Javascript Map class or a plain Object.

function validBraces(braces){
  const bracesMap = {"(":")", "{":"}", "[":"]"}  

Then we will declare a stack in the body of function. It will be an array and we will use push and pop to add and remove elements from top. This way we can track our progress as we progress with our iteration.

 const stack = []
 
  for (let brace of braces) {

First we check if the brace is in the keys of our map. If it is an opening brace - we push it to array. Notice that closing brackets will not satisfy this condition.

  if (bracesMap[brace]){
    stack.push(bracesMap[brace])

Then if our stack Is not empty and the last element is equal to the current brace we remove it from the stack. If the brace is not in our braces map, or if the stack is empty we return false.

  } else if (stack.length > 0 && stack[stack.length - 1] === brace){
    stack.pop()
} else {
    return false
  }
}

After iteration is over we check the length of our stack. If it’s empty it means each brace has a corresponding brace. Otherwise we return false

  return stack.length === 0
}

This approach has a time complexity of O(n) which is good. It only requires iterating over string elements array once.

What is a trace of running this test string of braces "[{[]}]" ?

[]
[ ']' ]
[ ']', '}' ]
[ ']', '}', ']' ]
[ ']', '}' ]
[ ']' ]
[]

Summary

This way our code is quite easy to read. I think it's clever and unintuitive to use stack. At first glance I feel like I should write set of complex rules and conditions to check if braces are closed properly. But here we iterate through our string array once and just track if any braces are left open in the end. How cool is that?