Skip to main content

20. Valid Parentheses

easyAsked at Linear

Determine whether a string of brackets is balanced. Linear uses this to see if you naturally reach for a stack and can explain the push/pop invariant clearly — a proxy for how you communicate data-structure choices.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Cited as an early-round warm-up in Linear phone screen reports.
  • r/cscareerquestions (2025-12)— Mentioned in a Linear SWE new-grad interview thread as a first-round problem.

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 must be closed by the same type of brackets, and open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

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: Closing bracket ] does not match open bracket (.

Approaches

1. Brute force repeated replacement

Repeatedly replace matched pairs () [] {} with empty strings until no replacements occur.

Time
O(n^2)
Space
O(n)
function isValid(s) {
  let prev = null;
  while (s !== prev) {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return s.length === 0;
}

Tradeoff: Intuitive but O(n^2) due to repeated string traversals. Good for explaining the invariant before pivoting to stack.

2. Stack (optimal)

Push open brackets; on a closing bracket, check that the top of the stack is the matching opener.

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: Single pass, linear time. The key insight: a stack naturally mirrors the LIFO nesting of bracket pairs. Return false if stack is non-empty at the end (unclosed openers).

Linear-specific tips

Linear engineers appreciate precise verbal reasoning. When you implement the stack solution, narrate the invariant: 'At any point, the top of the stack should be the most recently unclosed opener.' Also be explicit about the two failure modes — mismatched closer and unclosed opener — since many candidates only check one.

Common mistakes

  • Forgetting to check that the stack is empty at the end — a string like '(' passes the loop but is invalid.
  • Not handling the case where a closing bracket arrives when the stack is empty (stack.pop() returns undefined).
  • Using a simple counter (works for one bracket type) instead of a stack — fails for interleaved types like '([)]'.

Follow-up questions

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

  • Generate Parentheses (LC 22) — backtracking to produce all valid combinations.
  • Longest Valid Parentheses (LC 32) — DP or stack with index tracking.
  • What if you need to return the index of the first invalid character?

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 for multiple bracket types?

A counter can't distinguish '([)]' from '([])'. You need a stack to enforce that the most recent opener matches the current closer.

What if the string is empty?

An empty string has no unmatched brackets, so return true. The stack approach handles this naturally — the loop doesn't run, and the stack is already empty.

Can I use a map for the bracket pairs?

Yes — a closing-to-opening map is cleaner than multiple if/else branches and scales to additional bracket types without code changes.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →