Skip to main content

2. Valid Parentheses

easyAsked at PayPal

Given a string of brackets, decide whether they are balanced. PayPal asks this as a stack-comfort warm-up — the same data structure that powers their transaction-state-machine stack for rollback on failed payments.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Blind (2026-02)— Reported PayPal phone-screen question for backend SDE roles.
  • LeetCode Discuss (2025-09)— Recurring at PayPal Bangalore office.

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

Example 4

Input
s = "([)]"
Output
false

Explanation: Brackets close out of order.

Approaches

1. Brute force repeated replacement

Repeatedly replace '()', '[]', '{}' with empty string. If empty at the end, valid.

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

Tradeoff: O(n^2) due to repeated string scanning. Demonstrates intent but is too slow at scale.

2. Stack with closer-to-opener map (optimal)

Push openers. On closer, pop and verify it matches the expected opener. Empty stack at end = valid.

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). The stack mirrors PayPal's transaction-rollback semantics: last-pushed step is first-rolled-back.

PayPal-specific tips

PayPal grades you on edge cases: empty string, single bracket, odd-length string. Bonus signal: relate the stack to LIFO transaction state — when a payment fails mid-flight (auth → capture → settle), you roll back in reverse order, exactly like popping from a stack.

Common mistakes

  • Forgetting to check that the stack is non-empty before popping on a closer — fails on input ')'.
  • Returning true when the stack still has openers left (e.g., '(()').
  • Using string concatenation instead of an actual stack — leads to O(n^2).

Follow-up questions

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

  • What if brackets can be nested arbitrarily deep — is there a recursion-depth concern?
  • Add support for angle brackets '<>'.
  • Return the minimum number of insertions to make the string valid.

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 the stack work?

Bracket matching is LIFO: the most recently opened bracket must be the next one closed. A stack gives you O(1) push/pop with exactly that ordering.

Can I use a counter instead?

Only if there's one bracket type. With three types you must track the specific opener — a counter would accept '([)]' as valid.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →