2. Valid Parentheses

Q: Why does a counter fail?

A counter treats all brackets the same. '([)]' has equal opens and closes but mismatched nesting — only a stack tracks WHICH bracket is expected next.

Q: Could you do it in O(1) space?

Not in the general case — with k bracket types you need the stack to remember the order. The lower bound is the recursion depth.

easyAsked at Asana

Determine if a string of brackets is balanced and properly nested. Asana asks this to test whether you reach for a stack reflexively — the same data structure underpins their task-dependency cycle checks.

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

Source citations

Public interview reports confirming this problem appears in Asana loops.

Glassdoor (2026-Q1)— Frontend phone screen at Asana.
Blind (2025-09)— Mentioned as common Asana warmup before graph problems.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets and open brackets are closed in the correct order.

Constraints

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Examples

Example 1

Input

s = "()"

Output

true

Example 2

Input

s = "()[]{}"

Output

true

Example 3

Input

s = "(]"

Output

false

Explanation: Mismatched closer.

Approaches

1. Replace pairs repeatedly

Replace '()', '[]', '{}' with empty string in a loop until the string stops shrinking.

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

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

Tradeoff: Works but is O(n^2) from repeated string allocations. Don't lead with this.

2. Stack

Push openers; on closer, pop and confirm match. Empty stack at the end means valid.

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

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

Tradeoff: Linear time, single pass. The match-table lookup keeps the code tight.

Asana-specific tips

At Asana, the bonus signal here is connecting the stack pattern to their domain — they'll often follow up with 'how would you detect a cycle in a task-dependency graph?' which is the same stack-based DFS idea. State the connection out loud if you spot it.

Common mistakes

Forgetting to check the stack is empty at the end — '(((' returns true incorrectly.
Trying to pop from an empty stack on the first closer.
Using a single counter instead of a stack — fails on '([)]'.

Follow-up questions

An interviewer at Asana may pivot to one of these next:

What if you must return the index of the first unmatched bracket?
Handle nested brackets with arbitrary symbol alphabets.
Extend to validate JSON structure (LC 678 / 1003).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does a counter fail?

A counter treats all brackets the same. '([)]' has equal opens and closes but mismatched nesting — only a stack tracks WHICH bracket is expected next.

Could you do it in O(1) space?

Not in the general case — with k bracket types you need the stack to remember the order. The lower bound is the recursion depth.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →