Skip to content
Shubham JangleResources
Stacks

Explore topics

Valid Parenthesis

Watch the walkthrough
Open on Instagram

Problem

Decide whether a string containing only (), [], and {} has correctly matched and nested brackets.

Approach and revision checks

Push opening brackets, then require each closing bracket to match the top of the stack. At the end the stack must be empty. O(n) time and O(n) space. The imported implementation assumes bracket-only input; define separate behavior for other characters. Test empty input, an unmatched closer, and crossed pairs such as ([)].

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

2-valid-parenthesis.js

Original file on GitHub

var isValid = function (s) {
  const n = s.length;
  const stack = [];

  for (let i = 0; i < n; i++) {
    if (s[i] === "(" || s[i] === "{" || s[i] === "[") {
      stack.push(s[i]);
    } else {
      if (
        !stack.length ||
        (s[i] === ")" && stack[stack.length - 1] !== "(") ||
        (s[i] === "}" && stack[stack.length - 1] !== "{") ||
        (s[i] === "]" && stack[stack.length - 1] !== "[")
      ) {
        return false;
      }
      stack.pop();
    }
  }

  return stack.length === 0;
};

console.log(isValid("(){[]}"));
console.log(isValid("["));