Skip to main content

20. Valid Parentheses

easyAsked at eBay

eBay's backend services use expression parsers and template engines where bracket matching is foundational. This problem tests whether you can model state with a stack — a pattern that scales to validating JSON payloads, HTML templates, and complex search-query expressions used across eBay's marketplace platform.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-12)— Cited in eBay entry-level SWE interview reports as a stack fundamentals check.
  • Blind (2025-09)— eBay SWE interview threads list Valid Parentheses as a common phone-screen problem for early-career candidates.

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, open brackets must be closed in the correct order, and 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

Explanation: Each open bracket is immediately closed by the matching type in the correct order.

Example 2

Input
s = "([)]"
Output
false

Explanation: The brackets are interleaved incorrectly — '[' closes before '(' does.

Example 3

Input
s = "{[]}"
Output
true

Explanation: Properly nested: '{' contains '[' which closes before '}'.

Approaches

1. Stack with match map

Push open brackets onto a stack. When a close bracket is encountered, check that it matches the top of the stack. If it doesn't, or the stack is empty, return false. Return true only if the stack is empty at the end.

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

Tradeoff: O(n) time and space. The match map keeps the logic declarative — adding a new bracket pair requires only one map entry. This is the canonical solution eBay expects.

eBay-specific tips

State your stack invariant before coding: 'The stack holds unmatched open brackets; each close bracket must pair with the most recent open bracket.' eBay interviewers appreciate candidates who articulate the loop invariant. Don't forget the final stack-empty check — many candidates return true inside the loop on a perceived match and forget this step. At eBay's scale, this pattern underpins JSON schema validators and DSL parsers used in the seller listing pipeline.

Common mistakes

  • Forgetting to check stack.length === 0 at the end — an unclosed open bracket like '(' would incorrectly pass.
  • Calling stack.pop() before checking if the stack is empty — causes undefined comparisons.
  • Using a string or array of both open and close brackets instead of a clean close→open match map.
  • Not handling the odd-length early exit — if s.length is odd, it can never be valid (a small constant-time optimization).

Follow-up questions

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

  • Minimum Remove to Make Valid Parentheses (LC 1249) — remove the minimum number of brackets to make the string valid.
  • Longest Valid Parentheses (LC 32) — find the longest valid substring.
  • How would you validate a more complex expression with operators as well as brackets?

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 use a map keyed by close brackets instead of open brackets?

Keying by close bracket lets you check on close events directly — one lookup tells you the expected open bracket without needing a second conditional.

Can I solve this without a stack?

Not generally. A stack is the minimal data structure that captures the nesting relationship. Counter-based approaches only work for a single bracket type.

What is the space complexity in the best case?

O(1) if the string starts with a close bracket and returns false immediately, but O(n) in the worst case (all open brackets).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →