20. Valid Parentheses

In this tutorial we will solve 20. Valid Parentheses from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 20. Valid Parentheses

Problem statement

In this problem statement we are asked to check the validity of a given string s which consists of the following characters ( ) [ ] { }. The rule goes like the this. Open bracket must be closed by the same type of closing bracket. Open brackets must be closed in the same order. And every closing bracket has a corresponding opening bracket of the same type.

Example from leetcode.

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

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

Example 4:
Input: s = "([])"
Output: true

Constraints:

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Approach

To solve this problem we can use the stack data structure. Each time we encounter an opening bracket we will push the bracket into the stack. And each time we encounter a closing bracket we will pop an item from the stack and check if popped bracket is an opening bracket and of the same type as the closing bracket.

We can easily tell that the input string s is invalid if the length of the string is zero or odd.

Similarly, if we encounter a closing bracket and the stack is empty then we have an invalid input string.

Let us solve input s = "([])"

stack = []

index =  0 1 2 3
s     = "( [ ] )"
         ^

we have an opening bracket, so we push it into the stack.


stack = [
  "("
]

index =  0 1 2 3
s     = "( [ ] )"
           ^

we have an opening bracket, so we push it into the stack.


stack = [
  "(",
  "["
]

index =  0 1 2 3
s     = "( [ ] )"
             ^

we have a closing bracket, so we pop an item from the stack.
popped item = "["
is popped item (i.e., "[") an opening bracket? yes
is popped item (i.e., "[") matches the closing bracket type (i.e., "]") ? yes
since all conditions are satisfied, hence we proceed.


stack = [
  "("
]

index =  0 1 2 3
s     = "( [ ] )"
               ^

we have a closing bracket, so we pop an item from the stack.
popped item = "("
is popped item (i.e., "(") an opening bracket? yes
is popped item (i.e., "(") matches the closing bracket type (i.e., ")") ? yes

now, the stack is empty and we have processed all the characters of s

therefore, the input string s is valid.

Code

JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length === 0 || s.length % 2 !== 0) return false;
  
  const bracketPairs = {
    '(': ')',
    '{': '}',
    '[': ']'
  };
  let stack = [];
  for(let ch of s) {
    if (bracketPairs[ch]) stack.push(ch);
    else if (bracketPairs[stack.pop()] !== ch) return false;
  }
  return stack.length === 0;
};

Complexity

Time complexity: O(n)

If we have an input array of length n then we will have to process all of them and the time complexity will be O(n).

Space complexity: O(n)

In the worst case, we will have to save half of the input array of size n. Therefore the space complexity will be O(n/2) i.e., O(n).