The HackerRank Balanced Brackets problem is a classic interview question. Learning how to solve it is good practice for your data structures and algorithms experience.

The HackerRank problem tells us that a bracket can be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a match if the opening bracket occurs to the left of a closing bracket of the exact same type. There can be three types of matched pairs of brackets, [], {}, and ().

We are asked to write an isBalanced function that receives a string of brackets and returns a string of YES or NO, depending on whether the brackets are balanced or not.

To check for balanced brackets, we can use a stack data structure. We will use a JavaScript array to represent the stack. To add to the top of the stack, we will use the push method. To remove from the top of the stack, we will use the pop method.

We will also use a hash data structure to help us identify matching pairs of brackets. We'll associate closing brackets to their corresponding opening brackets. Then, when we encounter a closing bracket in the input string, we can check if the closing bracket matches one of the keys of the hash map. If it does, we can remove its corresponding value (the opening bracket) from the top of the stack.

Pseudo code solution

1. Define a hash map data structure of matching bracket pairs where each closing bracket maps to its matching opening bracket.
2. Define a stack as an array.
3. Loop over the length of the input string.
   • If an opening bracket is found, push it onto the stack.
   • If a closing bracket is found, pop the last element from the stack IF it is an opening bracket that matches the current closing bracket. keep iterating through the string.
   • If the current closing bracket does not match the opening bracket at the top of the stack, return "NO" because the brackets in the input string are not balanced.
4. If the stack is empty after iterating over the entire string, return "YES" because the input string has balanced brackets. If not, return "NO".

Code solution

function isBalanced(s) {
  const map = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  let stack = [];

  for (let i = 0; i < s.length; i++) {
    // check for opening bracket
    if (Object.values(map).includes(s[i])) {
      stack.push(s[i]);
    } else if (stack[stack.length - 1] === map[s[i]]) {
      stack.pop();
    } else {
      return 'NO';
    }
  }

  return stack.length === 0 ? 'YES' : 'NO';
}

Test cases

Let's test the isBalanced function above with the following test cases.

console.log(isBalanced('{[]}')); // "YES"
console.log(isBalanced('{{[[(())]]}}')); // "YES"
console.log(isBalanced('{[(])}')); // "NO"

Time and space complexity

The Big O time complexity of the solution is linear, or O(n), where n is the length of the input string. The solution used one loop that iterated over all the characters in the input string.

The Big O space complexity of the solution is linear, or O(n + o), where n is the size of the stack and o is the size of the hash map used to define matching bracket pairs. In a worst case scenario, there can be n characters from the input string on the stack.