JavaScript Coding Challenge: "Regular Brackets"

Regular Brackets Image

Today we're going to take a look at a very common challenge used in job interviews. This challenge is inspired by CodeSignal. Let's see what it says:

A bracket sequence is called regular if it is possible to insert some numbers and signs into the sequence in such a way that the new sequence will represent a correct arithmetic expression.

For a string consisting of only ('s and )'s, determine if it is a regular bracket sequence or not.

Example:

Given ()() we could insert (1 + 2) * (2 + 4) which is a valid arithmetic expression, but (())) is not as it has an extra closing bracket: ).

As you might notice, the problem doesn't seem so hard, but it might take a while to fully understand the way to approach it correctly.

First, let's write a function which will take as an input a string consisting of only round brackets:

function regularBrackets(brackets) {}

Now… let's use a loop to iterate through all these brackets:

function regularBrackets(brackets) {
    for (var i = 0; i < brackets.length; i++) {}
}

Let's also add a variable equal initialized with 0 which will be incremented every time we find an opening bracket and decremented every time we find a closing bracket. At the end, if equal will be 0 we'll know that we have a regular brackets sequence, otherwise we'll know that we don't have one. Pretty easy, right? 😇

function regularBrackets(brackets) {
    var equal = 0;
    for (var i = 0; i < brackets.length; i++) {
        brackets[i] === '(' ? (equal += 1) : (equal -= 1);
    }
    return equal === 0;
}

As you can see we used a ternary operator, as a shortcut for the if-else statements in the for loop. We check to see if the current bracket from the brackets string is an opening bracket… if it is, we increment equal by one, otherwise we decrement equal by one as it means that we have a closing bracket.

In the return statement, we check to see if equal is 0. If it is, that means that we have a valid regular brackets sequence and it returns true, otherwise it returns false.

Now let's test it:

1. regularBrackets('(((())))'); // returns true
2. regularBrackets('()(()'); // returns false
3. regularBrackets(')('); // returns true

Well… Everything is good for 1. and 2. but 3. is wrong, isn't it? Hmm… Why is that? 🤔 As you can see we have first a closing bracket, which is wrong and it should return false.

Well, that's because we haven't checked if our equal variable ever goes under 0. Because if it does, that means we have a closing bracket before an opening one.

Be aware as this is the tricky part of this challenge. This is why the interviewers like to use this challenge often.

To fix this we need a simple condition after our ternary operator that lies in the for loop, which will check if the equal variable ever becomes -1, and if it does, we're simply going to return false:

function regularBrackets(brackets) {
    var equal = 0;
    for (var i = 0; i < brackets.length; i++) {
        brackets[i] === '(' ? (equal += 1) : (equal -= 1);
        if (equal === -1) return false;
    }
    return equal === 0 ? true : false;
}

Perfect! Now this will work correctly for all the cases! Yey! 😄

Conclusion

We managed to get around with this problem by simply using a variable, but what about when we have multiple types of brackets like: (, [ and {? Can we solve this just by using a variable? Hmm… 🤔

Well... for this we're going to need to use a stack. 🤓 More about in the next article.

I hope you enjoyed this little challenge, and if you did, I'd appreciate if you share it with the world! 🌐

Happy coding! 😇

Tagged with javascript, challenge, beginner, codesignal, array, brackets