In this article, we will dive into one of the most frequently asked interview questions: the “Valid Parentheses” algorithm. You can find this problem in LeetCode here. This seemingly simple problem can be a stumbling block for many, but with the step-by-step walkthrough and in-depth explanation, at the end of this article, you’ll be able to approach it with confidence in your next interview.

Let’s take a look at the problem first.

Problem

Write a function that takes a string s as input, where s consists only the characters (, ), {, }, [ and ]. The function should determine if s is a valid string based on the following criteria:

Every open bracket must be closed by a bracket of the same type.
Open brackets must be closed in the correct order.
Each closing bracket must have a corresponding opening bracket of the same type.

Examples

Let’s take a look at some examples.

Example 1

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

Input: s = "{[]}"
Output: true

Example 6:

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

Example 7:

Input: s = "(})"
Output: false

Example 8:

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

Example 9:

Input: s = "])"
Output: false

Example 10:

Input: s = "()}"
Output: false

In each of these examples, the function takes the string s and returns true if it represents a sequence of open and close brackets that are correctly matched and in the proper order, and false otherwise.

Walkthrough

To address this challenge, we will utilise a stack as an array to keep track of opening brackets and ensure they correspond correctly with closing brackets.

The process involves iterating over each character in the string s. When encountering an opening bracket (i.e., (, {, or [), we will push it onto the stack.

For each closing bracket (i.e., ), }, or ]), we perform the following checks:

If the stack is empty at this point, it implies there’s no matching opening bracket for this closing bracket in s, and we return false.
If the stack is not empty, we compare the opening bracket at the last element in the stack with the current closing bracket. If they don’t match, we return false.
If the opening and closing brackets match, we will pop off the last element from the stack and compare the next bracket.

For instance, in Example 4 where s = "([)]", upon reaching the ), the stack will be like:

['(', '[']

and ) doesn’t match with the last element in the stack, [, leading to a return value of false.

If it’s true, we will keep traverse comparing each bracket by popping off the last element from the stack. In that way, we can progress next closing bracket and compare its corresponding opening bracket in the stack array.

After we have traversed the entire string:

If the stack is empty, we return true, indicating that all brackets have been correctly matched and popped off the stack. Remember we are popping off the last element from the stack.
If the stack is not empty, we return false, signifying that there are unmatched opening brackets remaining.

With this walkthrough, let’s solve this problem.

Implementation in JavaScript

Here is the complete code in JavaScript.

class Solution {
  isValid(s) {
    let stack = [];

    for (let character of s) {
      if (character === '(' || character === '{' || character === '[') {
        stack.push(character);
      } else {
        if (
          !stack.length ||
          (character === ')' && stack[stack.length - 1] !== '(') ||
          (character === '}' && stack[stack.length - 1] !== '{') ||
          (character === ']' && stack[stack.length - 1] !== '[')
        ) {
          return false;
        }

        stack.pop();
      }
    }

    return !stack.length;
  }
}

Implementation Steps

1. Let’s initialise a stack with an empty array. And we will iterate s and apply specific logics.

At the end, we will return either true of false depending on the stack’s status. If the stack is empty, it indicates that the parentheses are balanced, and we return true. Otherwise, an unempty stack suggests an imbalance, leading us to return false.

class Solution {
  isValid(s) {
    let stack = [];

    // Add logic here

    return !stack.length; 
  }
}

2. Let’s add the logics by iterating s so we will check each character in the given s value.

class Solution {
  isValid(s) {
    let stack = [];

    for (let character of s) {
      // Add logic here
    }

    return !stack.length; 
  }
}

3. Initially, let’s focus on handling opening brackets. Whenever we encounter an opening bracket in the string, our approach is to push this character onto the stack.

class Solution {
  isValid(s) {
    let stack = [];

    for (let character of s) {
        if (character === '(' || character === '{' || character === '[') {
            stack.push(character);
        } else {
            // Logic for closing bracket
        }
    }

    return !stack.length; 
  }
}

Let’s consider those three examples:

Example 8: ({[]}) – returning true
Example 4: ([)] – returning false
Example 9: ]) – returning false

For ({[]}), the first 3 opening brackets will be stored in the stack and the stack will look like:

['(', '{', '[']

For ([)], the first 2 opening brackets will be stored in the stack.

['(', '[']

For ]), there is no opening brackets, so nothing will be stored in the stack.

4. Now let’s check the closing brackets. As mentioned in the walkthrough section above, we will first check if the stack is empty, meaning there was no opening brackets prior, so we know the first character in the s is a closing bracket which should return false. This shows returning the false for ]) example.

Example 8: ({[]}) – returning true
Example 4: ([)] – returning false
~~Example 9: ]) – returning false~~

class Solution {
  isValid(s) {
    let stack = [];

    for (let character of s) {
      if (character === '(' || character === '{' || character === '[') {
        stack.push(character);
      } else {
        if (
          !stack.length
        ) {
          return false;
        }
      }
    }

    return !stack.length;
  }
}

5. If it’s not empty, we will check if the opening bracket at the last element of the stack matches the current closing bracket. If it doesn’t match, we will return false.

class Solution {
  isValid(s) {
    let stack = [];

    for (let character of s) {
      if (character === '(' || character === '{' || character === '[') {
        stack.push(character);
      } else {
        if (
          !stack.length ||
          (character === ')' && stack[stack.length - 1] !== '(') ||
          (character === '}' && stack[stack.length - 1] !== '{') ||
          (character === ']' && stack[stack.length - 1] !== '[')
        ) {
          return false;
        }
      }
    }

    return !stack.length;
  }
}

Let’s see the example 4 again ([)]. So the stack looks like:

['(', '[']

Now the next character we need to check is ) but the last element in the stack is [ and they are not a matching pair. So we will return false.

Example 8: ({[]}) – returning true
~~Example 4:~~ ~~([)] – returning false~~
~~Example 9: ]) – returning false~~

6. Finally if it matches, we will pop off the last element from the stack array because we no longer need to check and keep moving on checking the next closing bracket.

class Solution {
  isValid(s) {
    let stack = [];

    for (let character of s) {
      if (character === '(' || character === '{' || character === '[') {
        stack.push(character);
      } else {
        if (
          !stack.length ||
          (character === ')' && stack[stack.length - 1] !== '(') ||
          (character === '}' && stack[stack.length - 1] !== '{') ||
          (character === ']' && stack[stack.length - 1] !== '[')
        ) {
          return false;
        }

        stack.pop();
      }
    }

    return !stack.length;
  }
}

Let’s see the example 8, ({[]}).

So in the stack we will have:

['(', '{', '[']

And all closing brackets match with their corresponding opening brackets so it will pop off all elements from the stack. Once it traverses the entire s, and as the stack is empty, we will return true.

Python

class Solution:
  def isValid(self, s: str) -> bool:
    stack = []

    for character in s:
      if character in '({[':
        stack.append(character)
      else:
        if not stack:
          return False
        if (character == ')' and stack[-1] != '(') or \
           (character == '}' and stack[-1] != '{') or \
           (character == ']' and stack[-1] != '['):
          return False
        stack.pop()

    return not stack

Big O

Time complexity

The process has a time complexity of O(n). It is due to a single traversal through the string, where each character’s operation is executed in constant time.

Space complexity

The space complexity is O(n) too. It’s because the stack’s size grows linearly with the string’s length and the worst case scenario is when all the opening brackets are stored in the stack.