Skip to main content

2. Valid Parentheses

easyAsked at Datadog

Given a string of brackets, determine if every opener has a matching closer in the correct order. Datadog frames this as a streaming log-parser warmup — the same stack discipline shows up when validating JSON log payloads on a high-throughput ingestion pipeline.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • LeetCode Discuss (2026-Q1)— Datadog reports list this as a baseline screen question.
  • Glassdoor (2025-12)— Mentioned as a quick filter in Datadog phone screens.

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

Approaches

1. Repeatedly remove pairs

Strip out matched pairs '()', '[]', '{}' until no change; check if 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.length === 0;
}

Tradeoff: Quadratic — string rebuilding kills streaming throughput. Don't ship this at Datadog scale.

2. Stack single pass (optimal)

Push openers; on a closer, pop and check the match. At end, stack must be empty.

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

Tradeoff: Single pass, O(n) time. Stack depth bounds memory — same shape as Datadog's actual JSON validator chunks.

Datadog-specific tips

Datadog will probe whether you can stream-validate: 'What if the string is 10GB?' Mention bounded-depth tracking and the fact that the stack itself becomes a metric (nesting-depth-p99). Bonus signal: discuss recovery on malformed input rather than aborting the whole batch.

Common mistakes

  • Forgetting to check stack.length === 0 at the end — '(((' would falsely return true.
  • Popping when the stack is empty — undefined behavior, must handle.
  • Using string slicing instead of a stack — O(n^2) and not streamable.

Follow-up questions

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

  • Min Add to Make Parentheses Valid — count required insertions.
  • Longest Valid Parentheses — find longest matched substring.
  • Generate all valid parentheses of length 2n — backtracking variant.

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 a stack and not a counter?

A counter works only if there's one bracket type. With three types, you need to know which opener you're matching against.

How would you stream this?

The stack is already streaming-friendly — process char-by-char. Add a depth-limit guard so a pathological input can't blow memory.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →