Skip to main content

20. Valid Parentheses

easyAsked at JPMorgan

Given a string of brackets, decide whether every opener is matched by the correct closer in the right order. JPMorgan asks this as a phone-screen warm-up on the Software Engineer Programme because it is the smallest interesting use of an explicit stack and the easiest place to grade off-by-one mistakes.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— Repeated JPMorgan Software Engineer Programme phone-screen warm-up across UK and US new-grad reports.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Reddit r/cscareerquestions (2025-10)— JPMC SDE I phone-screen write-up lists this as the first 15-minute warm-up.

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. Every closer must correspond to the same type of opener.

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

Explanation: Square bracket closes before its matching round opener — order is wrong.

Example 5

Input
s = "{[]}"
Output
true

Approaches

1. Stack of openers with a pair-map (optimal)

Push every opener. On a closer, pop and check the popped opener matches the closer via a static {')':'(', ']':'[', '}':'{'} map. Reject on mismatch or pop-from-empty. Accept iff stack is empty at end.

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: O(n) time and O(n) worst-case space (all openers). Cannot do better than O(n) time because every character must be inspected, and you need at least the open-bracket depth in memory to verify ordering.

JPMorgan-specific tips

JPMorgan interviewers grade three things on this problem: (1) you choose a stack without prompting; (2) you check stack-non-empty before popping on a closer (the most common off-by-one); (3) you check the stack is empty at the end (handles unmatched openers like '(('). Stating those three invariants up front before writing code is what scores a strong-hire on the phone-screen rubric.

Common mistakes

  • Forgetting the final 'stack must be empty' check — wrongly accepts '(((' as valid.
  • Popping without first checking stack length — throws on a leading closer like ')'.
  • Using a counter instead of a stack — only works for a single bracket type, fails on '([)]'.
  • Building the pair map in the loop instead of as a constant — slower and uglier.

Follow-up questions

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

  • What if you also have to support angle brackets '<>'?
  • Generate all valid parentheses combinations of length n (LC 22).
  • Longest valid parentheses substring (LC 32) — same stack with index tracking.
  • Minimum add to make parentheses valid (LC 921).
  • What if the input is a stream and you must answer after every character?

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 instead of a counter?

A counter works for a single bracket type because the only invariant is 'never go negative, end at zero'. With multiple bracket types you must remember *which* opener is innermost, and that ordering information is exactly what a stack stores.

Can the space be reduced below O(n)?

No. In the worst case the string is all openers (e.g. '((((((') and you need the entire depth in memory before you can reject. O(n) is tight.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →