Valid Parentheses Problem

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

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

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

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

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();
...

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;
}

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 !