Skip to main content

2. Valid Parentheses

easyAsked at Palantir

Determine if a string of brackets is balanced and properly nested. Palantir uses this to probe whether you reach for a stack immediately, since their Foundry expression parser and ontology query language need balanced delimiter validation.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • LeetCode Discuss (2025-09)— Reported as Palantir FDE phone screen warm-up.
  • Glassdoor (2026-Q1)— Used to gate candidates before deeper ontology 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 brackets.

Approaches

1. Repeated string replacement

Keep replacing '()', '[]', '{}' with empty string until no change; check if result is empty.

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

Tradeoff: Quadratic and creates lots of garbage strings. Palantir interviewers want the stack.

2. Stack of expected closers

Push the matching closer when you see an opener; pop and compare when you see a closer.

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

Tradeoff: Linear time, single pass. Pushing the EXPECTED CLOSER (not the opener) saves a lookup at pop time.

Palantir-specific tips

Palantir grades this on whether you check stack.length === 0 at the end — many candidates miss the dangling-opener case. Mention that this is the same logic you'd use to validate AQL or PHQL expression nesting in the Ontology query layer. Push expected closers, not openers; if asked why, explain it eliminates the map lookup at pop time.

Common mistakes

  • Forgetting to check stack is empty at the end — string '((' returns true otherwise.
  • Popping from an empty stack — JavaScript returns undefined, which happens to work, but in Python it raises. Guard explicitly.
  • Building a Map inside the loop instead of outside — wastes allocations.

Follow-up questions

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

  • What if the alphabet includes multi-character tokens like '<<' and '>>'?
  • Return the index of the first invalid character instead of just true/false.
  • Generate all valid combinations of n pairs of parentheses (LC 22).

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 push the closer instead of the opener?

When you see a closer in the string, you can directly compare it against stack.pop() with no map lookup. It's a micro-optimization that signals you've thought about the inner loop.

Does this generalize to arbitrary nested structures like JSON?

The stack pattern generalizes, but JSON also has string-literal context where braces don't count. You'd need a tiny state machine that suspends bracket-tracking inside strings.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →