balancedBrackets

balancedBrackets.md

Prompt

Write a function that determines whether an input string has balanced brackets.

You are given an input string consisting of brackets—square [ ], round ( ), and curly { }. The input string can include other text. Write a function that returns either true if the brackets in the input string are balanced or false if they are not. Balanced means that any opening bracket of a particular type must also have a closing bracket of the same type.

An empty input string or a string without brackets is considered "balanced".

Examples

balancedBrackets(''); // true
balancedBrackets('[][(){}'); // false
balancedBrackets('({)}'); // false
balancedBrackets('({[]})'); // true
balancedBrackets('text ( is allowed ){rwwrwrrww [] ()}'); // true

Approach

A key thing to keep in mind is that the brackets can be balanced if they are right next to each other [] or if they are nested inside of a balanced brackets(they HAVE to be balanced as well) {([])}. You can also essentially ignore anything in the string that is not one of the 6 brackets we're looking for.

The optimal approach is to keep track of open brackets by using a Stack. As we come across closing brackets, if they match the most-recently-opened bracket we can pop the most-recently-opened bracket. If our stack is empty and we reach the end of the string, then our brackets must be balanced.

Interviewer Strategy Guide

• Some interviewees may take an extra step to filter out the non-bracket characters from the input string. This will most likely not affect the time/space complexity. It's fine if someone takes this step, but it is not necessary.

• If your interviewer struggles with an approach, ask them to list out the situations that would indicate that the input string is unbalanced. Remind them that this week focuses on stacks, queues, and linked lists. Would any of those structures be helpful here? What if you populated the data structure with open brackets and removed them when you found the corresponding closing bracket?

• Make sure your interviewer is considering edge cases. One example is the input ((). Their code may mistakenly return true for this situation if they do not consider that the stack must be empty at the end of their code for the string to be balanced. Similarly, if they are looking to count the number of brackets, cases such as ][)( could potentially return true when it should return false.

Step By Step Psudocode

• Store your matching brackets in a dictionary or hash.
• Implement a stack, which is key because of LIFO.
• Loop through the string.
• If our current element is an opening bracket, push it into our stack.
• Else if it is a closing bracket, do below checks. If its not a bracket, we just continue looping.
• If our stack is empty, then we know we hit a closing bracket before there are any opening brackets so we can simply return false right away. Else, we need to make a comparison with most recent opening bracket by popping it off of our stack.
• If the two brackets do NOT a match, return FALSE.
• If you get to the end of the loop and the stack has brackets (which means they are unmatched), return FALSE.
• Otherwise, our stack is empty and we've matched all the brackets so we can return TRUE.

Solutions

const balancedBrackets = (str) => {
  if (str == "") return true;

  const matchingBrackets = {
    "(": ")",
    "{": "}",
    "[": "]"
  };

  const stack = [];

  for (let i = 0; i < str.length; i++) {
    let curr = str[i]
    if (matchingBrackets.hasOwnProperty(curr)) {
      stack.push(curr);
    } else if (curr === ")" || curr === "}" || curr === "]") {
      if (stack.length === 0) return false;
      let lastElem = stack.pop();
      if (curr !== matchingBrackets[lastElem]) return false;
    }
  }
  
  return stack.length === 0;
}

Time Complexity - O(n), Space Complexity - O(n)

Another Similar Solution

const opens = {};
const closes = {};
([
  ['{', '}'],
  ['[', ']'],
  ['(', ')'],
]).forEach(([open, close]) => {
  opens[open] = close;
  closes[close] = open;
});

function balancedBrackets (str) {
  const opensStack = [];
  for (const ch of str) {
    if (opens.hasOwnProperty(ch)) {
      opensStack.push(ch);
    } else if (closes.hasOwnProperty(ch)) {
      const mostRecentOpen = opensStack.pop();
      const correspondingClose = opens[mostRecentOpen];
      if (ch !== correspondingClose) return false;
    }
  }
  return opensStack.length === 0;
}

Time Complexity - O(n), Space Complexity - O(n)

Here's a solution that doesn't use a stack which might be useful to know if your interviewee doesn't decide to use a stack. Instead of regex, you can loop through once to look for brackets and push them into a new array and then loop through again to check if they're balanced or not. As you can see with this approach, you're duplicating work.

const bracketPattern = /[[\](){}]/g;
const bracketPairs = { //keeps track of the possible bracket pairings
  '[' : ']',
  '(' : ')',
  '{' : '}'
};
function hasBalancedBrackets (inputString) {
  const inputBrackets = inputString.match(bracketPattern); // returns an array of all the brackets in the input
  const brackets = [];
  if (!inputString.length || !inputBrackets.length) {
    return true; // empty input or no brackets i.e. 'balanced' (throwing an error is fine also)
  }
  inputBrackets.forEach(function (bracket) {
    const lastBracket = brackets[brackets.length - 1];
    if (bracketPairs[lastBracket] === bracket) { // the current bracket and the last bracket are a pair
      brackets.pop(); // we found a pair so remove the opening bracket from the array and move on
    } else {
      brackets.push(bracket);
    }
  });
  return brackets.length === 0; // if the brackets were balanced then we should not have any brackets in the array
}

Resources

• Interviewees can attempt this at LeetCode: https://leetcode.com/problems/valid-parentheses/ or on a repl.
• This problem is available at AlgoExpert under the name "Balanced Brackets"