loading...
Cover image for Valid Parentheses Problem

Valid Parentheses Problem

leamsii profile image Liam Escribano ・2 min read

How to solve the Valid Parentheses Problem in JavaScript

What is the Parentheses Problem?

Your function is passed a string of brackets. If each open bracket in the string has a corresponding closing bracket and they're in the correct order, then this is considered a balanced string of brackets.

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
"[]"        // Valid
"}{"        // Invalid
"{({[]})}"  // Valid
"{({[]}))"  // Invalid
Enter fullscreen mode Exit fullscreen mode

Our Approach

We're going to be using a Stack to solve this problem. JavaScript doesn't have Stacks by default but a simple Array gives us enough of the original Stack functionality to make this work. This array will follow a LIFO (Last In First Out) behavior.

Pseudo-code

Let's try to solve this example using plain old English

'[{()}]'

  1. Iterate over the entire string once
  2. For every open bracket we push it to the stack
  3. For every closed bracket we get the last open from the stack
  4. If both the closing and opening brackets match we pop
  5. If they don't, we end the loop and return false

Time to Code

excited

const stack = []
const brackets = {'(':')', '[':']','{':'}'}
Enter fullscreen mode Exit fullscreen mode

We created our first data structures. An array to act as our stack and an Object to map our brackets.

for (let i = 0; i < str.length; i++) {
        const currentBracket = str[i];

        if (brackets[currentBracket]) {
            stack.push(currentBracket)
...
Enter fullscreen mode Exit fullscreen mode

Here we create a basic for-loop to iterate over our entire string. For every bracket we find we push it to the top of the stack only if is an open bracket.

const lastOpenBracket = stack[stack.length - 1];
if (brackets[lastOpenBracket] != currentBracket) {
    return false;
}
stack.pop();
...
Enter fullscreen mode Exit fullscreen mode

If the current bracket is not open then it must be a closed bracket. We grab the last open bracket from our stack and compare them. If the pair doesn't match, we return false. If they do, we pop the stack and continue.

Here's the entire code;

function isValid(str) {
    const stack = []
    const brackets = {'(':')', '[':']','{':'}'}

    for (let i = 0; i < str.length; i++) {
        const currentBracket = str[i];

        if (brackets[currentBracket]) {
            stack.push(currentBracket)

        } else {
            const lastOpenBracket = stack[stack.length - 1];
            if (brackets[lastOpenBracket] != currentBracket) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.length === 0;
}
Enter fullscreen mode Exit fullscreen mode

Congratulations !

We just solved the Valid Parentheses Problem. This question was a very common interview question back in the old days but its still relevant today and we can learn a lot from it. Hope you enjoyed this read, happy coding !

Discussion

pic
Editor guide