Valid ParenthesesEasy

Given a string containing '(', ')', '{', '}', '[', ']', determine if the brackets are balanced and correctly nested.

Examples

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

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

Input: s = "([)]" → Output: false — wrong nesting order

Approach

A stack is the natural fit because nesting is inherently last-in-first-out: the most recently opened bracket must be the next one closed. Push every opening bracket. On a closing bracket, pop the stack and check it matches — a mismatch (or an empty stack when you expected something to pop) means invalid immediately. At the end, a non-empty stack means something was never closed.

Complexity — best & worst case

Time O(n) worst case (fully balanced, scan everything), O(1) best case (first character is an unmatched closing bracket)

Space O(n) worst case — all opening brackets, e.g. "(((((("

Code

// Given a string of '(', ')', '{', '}', '[', ']', determine if the
// brackets are balanced and correctly nested.

// There isn't really a "brute force" version of this one — the stack
// IS the efficient approach, and trying to solve it without one
// (e.g. repeatedly deleting "()"/"{}"/"[]" pairs) is both slower and
// messier, but included below for comparison.

// --- Alternative: repeatedly strip innermost pairs (O(n^2)-ish) ---
function isValidStrip(s) {
  let prevLength;
  do {
    prevLength = s.length;
    s = s.replace("()", "").replace("[]", "").replace("{}", "");
  } while (s.length !== prevLength);
  return s.length === 0;
}

// --- Optimal: push opening brackets, pop and match on closing ones ---
function isValid(s) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    } else {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.length === 0;
}

// --- Example Usage ---
console.log(isValid("()[]{}")); // true
console.log(isValid("(]"));     // false
console.log(isValid("([)]"));   // false, wrong nesting order
console.log(isValid("{[]}"));   // true
console.log(isValidStrip("{[]}")); // true