Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in JavaScript

Solution Review: Balance Parenthesis

Explore how to use recursion to determine if an array of parentheses is balanced. Learn the role of tracking indices and base cases to match opening and closing symbols correctly. This lesson helps you apply recursion techniques to solve common array problems in coding interviews.

We'll cover the following...

Solution: Using Recursion

Javascript (babel-node)
function balanced(testVariable, startIndex = 0, currentIndex = 0) {
  // Base case1 and 2
  if (startIndex == testVariable.length) {
    return currentIndex == 0
  }
  // Base case3
  if (currentIndex < 0) { // A closing parenthesis did not find its corresponding opening parenthesis
    return false
  }
  // Recursive case1
  if (testVariable[startIndex] == "(") { 
    return balanced(testVariable, startIndex + 1, currentIndex + 1)
  }
  // Recursive case2
  else if (testVariable[startIndex] == ")") { 
    return  balanced(testVariable, startIndex + 1, currentIndex - 1)
  }
  else {
    return false // the string contained an unrecognized character
  }
}
// Driver Code
testVariable = ["(", "(", ")", ")", "(", ")"]
console.log("The array [\"(\", \"(\", \")\", \")\", \"(\", \")\"] is balanced: " + balanced(testVariable))
testVariable = ["(", "(", ")"]
console.log("The array [\"(\", \"(\", \")\"] is balanced: " + balanced(testVariable))

Explanation

Our task is to read an array of parentheses from left to right and decide whether the symbols are balanced.

To solve this problem, notice that the most recent opening parenthesis must match the following closing parenthesis. The first opening parenthesis processed will be saved until the very last parenthesis is processed to find its corresponding closing parenthesis.

Closing parentheses match opening parentheses in the reverse order of their appearance, meaning that they match from the inside out. This is a clue that recursion can be used to solve this problem.

Let’s investigate the code snippet above.

The two variables startIndex and currentIndex are important to note. startIndex traverses the whole array. In each recursive call, it moves to the next element in the array. It is also used to check whether or not we have reached the end of the array.

The currentIndex examines if each opening parenthesis has a corresponding closing parenthesis. If we encounter a closing parenthesis currentIndex ...