23. Valid Parentheses

easyAsked at Doordash

Validate bracket nesting with a stack — Doordash treats this as a warmup for stack reasoning, which surfaces in their order-processing pipeline and nested-menu parsing logic.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given a string s containing only '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: open brackets are closed by the same type, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket.

Constraints

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'
Returns true only if perfectly matched and ordered

Examples

Example 1

Input

s = "()[]{}"

Output

true

Example 2

Input

s = "([)]"

Output

false

Explanation: Interleaved brackets are not valid.

Approaches

1. Brute force repeated replacement

Repeatedly replace '()', '[]', '{}' with empty string until no change; string is valid if it reduces to empty.

Time: O(n^2)
Space: O(n)

function isValid(s) {
  let prev;
  do {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  } while (s !== prev);
  return s.length === 0;
}

Tradeoff:

2. Stack with hash map

Push open brackets onto a stack; for each close bracket verify the top of the stack is its matching open bracket. O(n) single pass.

Time: O(n)
Space: O(n)

function isValid(s) {
  const stack = [];
  const match = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) {
      stack.push(ch);
    } else {
      if (stack.pop() !== match[ch]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff:

Doordash-specific tips

Doordash uses this to warm up your stack intuition before harder problems like min-bracket removal or nested order validation. The key insight to voice aloud: the stack always holds the expected closing bracket — some candidates store the open bracket and look up the closing; storing the expected closer makes the check a single comparison. They'll sometimes extend this to 'validate a nested JSON-like order descriptor' — the same stack logic applies.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Valid Parentheses and other Doordash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →