Recursion for Coding Interviews in JavaScript/

...

/

Solution Review: Balance Parenthesis

Solution Review: Balance Parenthesis

This review provides a detailed analysis of the solution to determine whether or not an array contains balanced parenthesis.

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 ...