Skip to main content

2. Valid Parentheses

easyAsked at ServiceNow

Given a string of brackets, decide if every opener has a matching closer in the correct order. ServiceNow asks this to confirm you reach for a stack — the same data structure their workflow engine uses to nest sub-flows and rollback approval steps.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2026-Q2)— SDE phone-screen rotation lists this alongside Two Sum.
  • Blind (2025-09)— ServiceNow new-grad interviews cite stack-based parsing as a recurring warm-up.

Problem

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if open brackets are closed by the same type, open brackets are 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

Example 2

Input
s = "()[]{}"
Output
true

Example 3

Input
s = "(]"
Output
false

Explanation: Mismatched bracket types.

Approaches

1. Repeated string replace

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

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

Tradeoff: Cute but quadratic. Mention only as the anti-pattern — string allocation cost dominates.

2. Stack with pair-lookup map

Push openers. On a closer, peek the stack: if it matches the expected pair, pop. Otherwise return false.

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: Linear time. The pair-lookup map is cleaner than nested if/else and is the pattern ServiceNow uses in their nested workflow validator.

ServiceNow-specific tips

ServiceNow grades for the LIFO insight and clean stack mechanics — they map this directly to how their Flow Designer nests approval steps. Bonus signal: end with 'stack.length === 0' instead of just 'true' to catch unclosed openers, which is exactly the bug their workflow engine guards against on incomplete subflows.

Common mistakes

  • Returning true at end without checking stack.length === 0 — fails on '(((' input.
  • Comparing in the wrong direction: pairs[stack.pop()] vs pairs[ch].
  • Using a string instead of array as the stack — works but O(n) pop on string concat.

Follow-up questions

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

  • Add a fourth bracket type like '<>'.
  • Return the index of the first invalid bracket.
  • Minimum insertions to make a parentheses 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 approach work?

Brackets nest, so the most recently opened bracket must close first — that's the LIFO property of a stack. Every time we hit a closer, it must match the top of the stack.

What's the worst-case input?

An all-openers string like '(((((((' — the stack grows to size n. The space is bounded by input length, so O(n) is the worst case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →