Akhil

Posted on

# Valid parentheses, solving a Facebook interview question.

This is one of the most commonly asked screeing questions, Especially if the interview is conducted by Hackerrank, there's a good chance that they will ask this question. I was asked this exact same question 4 times by Hackerrank.

Question : Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
An empty string is considered valid.

Eg:

``````   string = "()[]{}"              //valid
string = "[{()]}"              //invalid
string = ""                    //valid
``````

Let's solve this,

At its bare minimum, the question is asking us to find matching opening and closing parentheses. So for :
"(", ")" is the valid closing parentheses
"{", "}" is the valid closing parentheses
"[", "]" is the valid closing parentheses

Or in other words, we can say that the "pairs" cancel out each other, from this we can say that the order matters.

A good data structure that will help us with :
1 > Storing the parentheses and cancel them when the match is found,
2 > Keeping track of parentheses

is Stack. We shall push the opening parentheses on to the stack and pop it when we encounter a closing parenthesis, and that the same time we can check if the closing parenthesis is the valid match for the parentheses being popped.

## Implementation - 1

Here we can make a small optimization of checking if the length is even if it's not then obviously the string is not valid.
Converting the above idea into code :

``````var isValid = function(S) {
let stack = [];
if(S == '') return true;
if(S%2 != 0) return false;
for(let s of S){
if(s == '(' || s == '{' || s == '['){
stack.push(s);
}else{
if(stack.length == 0) return false;
let c = stack.pop();
if(c == '(' && s != ')'){
return false;
}
if(c == '{' && s != '}'){
return false;
}
if(c == '[' && s != ']'){
return false;
}
}
}

if(stack.length != 0) return false;      // for conditions like "{([])}}}"
return true;
};
``````

Now this works well, but can we do better? There are a lot of if-else conditions just for checking the "pairs". Let's try to make it more concise.

## Implementation - 2

Since the main work of the if conditions are to match the parentheses, we use another data structure, the Hashmaps.

Since a closing parenthesis must match with a corresponding opening parenthesis, we create a mapping between closing and opening parenthesis.

So the algorithm works this way :
1 > Check if the current symbol is in the hashmap, if not the push it on the stack.
2 > If the current symbol is in the hashmap, then pop from the stack and compare it with the value corresponding to hashmap entry.

So if the top of the current symbol is ")" then we pop from the stack, compare the popped value with the value corresponding to ")" in hashmap which is "(", if they arent same then the string is not valid.

The code will make it a lot clear.

``````var isValid = function(S) {

if(S == '') return true;
if(S.length%2 != 0) return false;

let map = {};
map[")"] = "(";
map["}"] = "{";
map["]"] = "[";

console.log(map);

let stack = [];
for(let s of S){
if(!map[s]){
stack.push(s);
}else{
if(stack.length == 0) return false;
let c = stack.pop();
if(c != map[s]) return false;
}
}

if(stack.length !=0) return false;
return true;
};
``````

I hope you liked my explanation if you know a better way of solving this problem then please share it with us :)

Nam Hoang Le • Edited

You can check a number is not equal to zero by `if (n) {}` or check empty string by `if (!s) ...`.
Of course, just use object literal for you `map`. :)

The last statement should be `return !stack.length`.

Bonus point: we can solve it shorter by using recursion and String replace method.

Akhil

I wrote this way for code readability :)

Nam Hoang Le • Edited

Yes, that way is better for products. But the boundary between readability and cleaning is not always clear. :)

Akhil

True that.

JS Bits Bill

Also tried the standard `for` loop approach which actually proved easier to deal with than `every`:

``````const isValid = function(s) {

const pairs = {
'(': ')',
'[': ']',
'{': '}'
};

const openParens = [];
for (let i = 0; i < s.length; i++) {
const endParen = pairs[s[i]];

if (endParen) openParens.push(endParen);
else if (openParens[openParens.length - 1] === s[i]) openParens.pop();
else return false;
}

return openParens.length ? false : true;
};
``````

Akhil

Awesome work man ! keep up !

Nam Hoang Le

Itโs me again. Hereโs my solution.

``````function isValid(s) {
const t = s.replace(/\(\)|\[\]|\{\}/g, "");
return s == t ? !s : isValid(t);
};
``````

Akhil

Test it here: leetcode.com/problems/valid-parent...

As far as I know, the regex will manipulate string and string manipulation is a bit time consuming heavy in javascript.

But smart and concise code though !

Nam Hoang Le • Edited

Itโs true. C/C++ can solve it in almost 0ms.

JS Bits Bill • Edited

I gave this a shot! Similar to yours, my approach was to split the string and track the expected closing parens in a separate array. I used the `every` method instead of a `for...of` loop which works nicely with the empty string case.

``````const isValid = function(str) {

const pairs = {
'(': ')',
'[': ']',
'{': '}'
};

const closingParens = [];
return [...str].every(validate);

function validate(char, i, arr) {
const isLastChar = i === arr.length - 1;

// If char found in pairs, push closing paren to arr
if (pairs[char] && !isLastChar) {
closingParens.push(pairs[char]);
return true;

} else {
// If char has no closing paren, return false
if (!closingParens.length) return false;

// Check if current char is last in arr
const lastCharInArray = closingParens.pop();

// If last char and unmatched parens, return false
if (isLastChar && closingParens.length) return false;

// If pair found, continue
if (char === lastCharInArray) return true;
}
}
};
``````

What do you think?

Akhil

For :"{[]}" it returns false.

Try solving it here : leetcode.com/problems/valid-parent...

JS Bits Bill

@akhil I updated it to meet that condition!

I conduct interviews (not at Facebook), I don't ask questions about algorithms, but I wouldn't probably hire someone who writes code like that, especially if it's a mid-senior position, because there are too many bad practices:

• `var` shouldn't be used anymore;
• variables should have more descriptive names and start with a lowercase character;
• always `===`, never `==`;
• static constants should be defined outside functions;
• `renturn stack.length === 0` is cleaner.

I wrote the implementation below and I find it much cleaner.

``````const CLOSING_BRACKET_BY_MATCH = {
'(': ')',
'[': ']',
'{': '}',
};

const testBrackets = (input) => {
const stack = [];
let len = 0;

if (input.length % 2 !== 0) {
return false;
}

for (const character of input) {
if ('([{'.indexOf(character) !== -1) {
stack.push(character);
len += 1;
} else {
const lastCharacterPushed = stack[len - 1];

if (len === 0 || (CLOSING_BRACKET_BY_MATCH[lastCharacterPushed] !== character)) {
return false;
}

stack.pop();
len -= 1;
}
}

return len === 0;
};
``````

mayank joshi

Amazing post. I loved the concept.๐ฅณ

Just one thing, try moving this from webdev to #algorithms tag for better reach among algo geeks.

Akhil

My bad, it was meant to be #tutorial.

Thanks a lot for reading :)