Javascript | Valid Parentheses

Interview Question

Please subscribe my youtube channel: FrontEnd Interview Preparation: https://www.youtube.com/channel/UC-elmWUfbcbmvuhlS12nCtg

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

Input: s = "(((]]"
Output: false

Example 2:

Input: s = "((((([)]"
Output: false

We will see two implementations, Let's, deep dive -

• arr is an array where we push ( ‘(’, ‘[’, ‘{’ ),
• arr[arr.length — 1] checks for the last element in the array.
• when the char = “)” and if the last element in the array(stack) matches with the opposite of “(”, then pop the element.
• if the stack has no char left in the array, then the string is valid.

First Implementation,

/**
 * @param {string} s
 * @return {number}
 */
var isValid = function(s) {
      const arr = [];
for(let char of s) {
    if(char === ")" && arr[arr.length - 1] === "(") {
      arr.pop();
    } else if(char === "]" && arr[arr.length - 1] === "[") {
      arr.pop();
    } else if(char === "}" && arr[arr.length - 1] === "{") {
      arr.pop();
    } else {
      arr.push(char);
    }
    
  }
return arr.length === 0
};

See the output

Second Implementation,

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = {
        ")": "(",
        "]": "[",
        "}": "{"
    }
    let arr = [];
    
    for(let i = 0; i < s.length; i ++){
        if(s[i] === "(" || s[i] === "[" || s[i] === "{"){
            arr.push(s[i]);
        }
        else{
            if(arr[arr.length - 1] === map[s[i]]){
                arr.pop();
            }
            else return false;
        }
    }
    return arr.length === 0 ? true : false;
};

See the output

This problem is very popular in coding interviews.

Keep learning, keep growing!

Don’t forget to follow me for more such articles, and subscribe to our newsletter.

Let’s connect on LinkedIn!. Please read more for more data structure javascript questions.

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer