Skip to main content

2. Valid Parentheses

easyAsked at Databricks

Determine if a string of brackets is balanced. Databricks asks this to see if you reach for a stack instinctively and whether you can map it onto SQL-parser or query-AST validation scenarios.

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Blind (2025-09)— Databricks SQL team phone screen warm-up.
  • LeetCode Discuss (2026-Q1)— Tagged Databricks; followed by 'how would you validate Spark SQL parens at parse time?'

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 in the correct order. Every closing 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. Replace pairs until empty

Repeatedly strip '()' '[]' '{}' until no change.

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: Cute but quadratic and allocates many strings. Don't ship this.

2. Stack of expected closers

For each opener, push the matching closer onto a stack. For each closer, it must equal the top of the stack.

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

Tradeoff: Linear time, single pass. Pushing the expected closer (not the opener) avoids a second lookup table.

Databricks-specific tips

Databricks interviewers grade this on whether you reach for a stack without prompting and whether you can extend it to multi-character delimiters (like SQL block comments /* */). Bonus signal: articulating that this is the same pattern Spark Catalyst uses to validate query ASTs before logical planning. Don't over-engineer — the elegance is the point.

Common mistakes

  • Forgetting the final 'stack.length === 0' check — '(' alone returns true otherwise.
  • Pushing the opener and decoding on each closer instead of pushing the expected closer.
  • Not handling the empty-stack case when a closer arrives first — stack.pop() returns undefined which luckily != c, but be explicit.

Follow-up questions

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

  • Add support for '<' '>' (XML-style).
  • Return the index of the first invalid character.
  • Scale to streaming input — can you detect imbalance early and short-circuit?

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, not the opener?

Saves a lookup table at decode time. You'd otherwise need a second map from closer to opener at every closer.

Could a regex solve this?

No — balanced-bracket languages are context-free, and standard regex is regular. PCRE recursive patterns can, but a stack is clearer.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →