← Back to posts

Valid Parentheses

March 15, 20251 min read

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

Description

You get a string of parentheses and have to check that every opened one is closed, in the right order ex: 1.Input: "()" -> true 2.Input: "()[]{}" -> true 3.Input: "(]" -> false

Assumptions

input is only made of parentheses (}]){[ and has at least 2 chars

Approach

Although there are many ways to solve this, let's focus on the most evident and easy to implement, which is using the appropriate data structure, a stack. Because in JavaScript we don't really have a stack, we are going to use an array and keep adding or removing elements at the end, which gives us Last-In-First-Out (LIFO) behavior.

Solution

function validParentheses(param) {
  //valid input is made only of "()[]{}" and has at least 2 chars, so we don't have to do additional checks

  // maps each closing bracket to its opening bracket
  const parenthesesMap = new Map()
  parenthesesMap.set(")", "(");
  parenthesesMap.set("]", "[");
  parenthesesMap.set("}", "{");

  const bufferStack = [];
  for (const c of param) {
    if (parenthesesMap.has(c)) {
      // closing bracket: it has to match the last opened one
      if (bufferStack.pop() !== parenthesesMap.get(c)) {
        return false;
      }
    } else {
      bufferStack.push(c)
    }
  }
  return bufferStack.length === 0;
}

Explanation

We know the input only contains three types of parentheses: (), [], and {}. We use a stack (bufferStack) to keep track of the opening parentheses as we iterate over the string. For each character in the string:

If the character is a closing bracket, we pop the top of the stack. If that isn't the matching opening bracket (looked up in parenthesesMap), the string is invalid and we return false.
If it is an opening bracket, we push it onto the stack. At the end, if the stack is empty, every opening bracket was matched by its closing bracket and the input string is valid. If something is left in the stack, those brackets were never matched.

Complexity

It runs in O(n) time because the loop makes a single pass over the string. The stack is what checks that the brackets are paired and nested correctly.

Reference