Skip to main content

20. Valid Parentheses

easyAsked at Shopify

Shopify uses Valid Parentheses to test whether you instinctively reach for a stack on a matching-pairs problem. Expect the follow-up to extend to template strings or Liquid-style nested tags — Shopify's storefront templating engine — so the data-structure choice has to scale.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Backend Developer + Engineering Lead phone screens list Valid Parentheses as a warm-up; follow-up often involves nested template tag validation.
  • Reddit r/cscareerquestions (2025-11)— Shopify internship + new-grad reports cite this as a 10-minute first-round screen.

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

Example 4

Input
s = "([)]"
Output
false

Example 5

Input
s = "{[]}"
Output
true

Approaches

1. Repeated removal of inner pairs (brute-force)

Repeatedly strip the innermost '()', '[]', or '{}' pairs until the string stops changing. Valid iff the final string is empty.

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

Tradeoff: Conceptually clear and one-liner-ish, but each replace scans the string and we may need up to n/2 passes. Shopify will accept this only as a starting point — name it, then ditch it.

2. Stack (optimal)

Push openers onto a stack; on each closer, pop and verify the match. Valid iff the stack is empty at the end.

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, single pass, O(n) worst-case stack depth (all openers). The canonical answer and what Shopify expects on the whiteboard. The pairs map keeps the matching logic to one line — easier to extend when the interviewer adds template tags.

Shopify-specific tips

Shopify's likely follow-up: 'extend this to validate nested template tags like {% if %}...{% endif %}'. Be ready to generalize the pairs map and parse multi-character tokens. The interviewer is checking whether your stack-based mental model survives a real-product extension, not just brackets.

Common mistakes

  • Returning true the moment the stack hits zero — you must wait until the entire string is consumed (input '()(' should return false).
  • Popping from an empty stack without a guard — JavaScript returns undefined, which can accidentally equal pairs[ch] only if pairs[ch] is also undefined.
  • Iterating with s[i] vs s.charAt(i) inconsistently and confusing the bounds check.
  • Trying to count opens vs closes (works for one bracket type, fails for mixed types like '([)]').

Follow-up questions

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

  • Extend to multi-character tags (e.g. validate {% if %}...{% endif %} nesting).
  • Return the index of the first invalid character, not just a boolean.
  • What if the input can contain other characters that should be ignored?
  • Generate all valid parentheses of length 2n (LeetCode 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 is stack the right data structure here?

Bracket matching is LIFO — the most recently opened bracket must close first. A stack gives you O(1) push/pop and naturally encodes 'innermost-first', which is exactly the validation rule. No other structure makes the nesting check trivial.

What's the worst-case stack depth?

n/2, hit by strings like '((((((' where every char is an opener. The interviewer may ask whether you can do O(1) extra space — for arbitrary mixed brackets, no, because you must remember every unmatched opener's type.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →