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 Sam K., 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.

More ServiceNow coding interview questions

See all ServiceNow problems →

Companies that also ask Valid Parentheses