Skip to main content

2. Valid Parentheses

easyAsked at Coinbase

Determine if a string of brackets is balanced and properly nested. Coinbase uses this to test stack fundamentals — order-book matching engines lean on the same LIFO discipline.

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

Source citations

Public interview reports confirming this problem appears in Coinbase loops.

  • Glassdoor (2026-Q1)— Coinbase backend warm-up on phone screens.
  • LeetCode Discuss (2025)— Frequently reported by Coinbase candidates as a 15-minute opener.

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. 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

Approaches

1. Repeated string replacement

Repeatedly replace '()', '[]', '{}' with empty until none left; check if string is empty.

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

Tradeoff: Cute but O(n^2) due to string immutability. Mention only as a starting point.

2. Stack with matching-pair map

Walk the string. Push opens onto a stack; on a close, pop and verify the popped open matches the expected pair. At the end the stack must be empty.

Time
O(n)
Space
O(n)
function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff: Single pass, O(n) time. The bracket-matching pattern shows up in expression parsers, nested-message validation, and JSON streaming.

Coinbase-specific tips

Coinbase wants the stack pattern recognized instantly — they often follow up with 'how would you stream this from a socket without buffering?' Be ready to discuss a chunked variant where the stack persists across chunks. They also probe edge cases (empty string, single close) to see if you guard before popping.

Common mistakes

  • Calling stack.pop() on an empty stack without guarding — returns undefined and may silently pass.
  • Forgetting to check that the stack is empty at the end — '((' returns true otherwise.
  • Using a Set for openers and rebuilding the pair lookup on every close — gratuitous work.

Follow-up questions

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

  • Stream version — bytes arrive in chunks; keep the stack between calls.
  • Allow extra characters (letters, whitespace) between brackets and ignore them.
  • Return the index of the first unmatched bracket instead of just true/false.

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 not count opens vs closes?

Counting ignores type and order. '([)]' has equal counts but is invalid — only a stack captures both type and nesting order.

What if the input is enormous?

O(n) time and O(n) space scale fine to millions of chars. If you need streaming, pass the stack between chunks; the only state is the stack itself.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →