20. Valid Parentheses

easyAsked at IBM

Valid Parentheses is IBM's stack-pattern screener. The interviewer is grading whether you recognize the stack signature (matching pairs of arbitrary depth), whether you handle the closer-without-opener and unclosed-tail edge cases, and whether you finish in O(n) on a single pass.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— Recurring IBM SWE-1 and SWE-2 phone-screen problem.
LeetCode (2026-Q1)— Top-30 IBM-tagged problem.
GeeksforGeeks (2025-11)— Cited in IBM interview-experience archive.

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 must be closed by the same type of brackets, open brackets must be 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

Example 4

Input

s = "([])"

Output

true

Example 5

Input

s = "("

Output

false

Explanation: Unclosed opener at the end is invalid.

Approaches

1. Repeatedly remove adjacent pairs

Loop until the string is empty or unchanged, replacing '()', '[]', '{}' with empty strings each pass.

Time: O(n^2)
Space: O(n)

function isValidNaive(s) {
  let prev = null;
  while (prev !== s) {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return s.length === 0;
}

Tradeoff: Conceptually correct and a useful first-attempt. Allocates a new string per pass — quadratic at scale. Mention this only to dismiss it and move to the stack solution.

2. Stack of openers (optimal)

Push openers; on each closer, pop and verify the popped opener matches. Final stack must be empty.

Time: O(n)
Space: O(n)

function isValid(s) {
  const pair = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  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, O(n) space worst case (all openers). The stack-pattern is the canonical answer; the lookup table keyed by closer is the standard implementation choice — cleaner than a chain of if-else.

IBM-specific tips

IBM grades two specific moves: (1) you recognize stack as the data structure unprompted (signals you've seen the pattern), (2) you handle both the 'closer with no opener' case AND the 'unclosed openers at the end' case — many candidates ship only one and lose points. Saying 'the answer is true iff every closer matches a popped opener AND the stack is empty at the end' before coding earns the rubric checkbox.

Common mistakes

Forgetting the final `stack.length === 0` check — returns true for unclosed openers like '(('.
Popping the stack without checking it's non-empty first — `stack.pop()` returns undefined on empty, which luckily mismatches every opener but is fragile.
Using two separate stacks (one for type, one for position) when one stack suffices.
Hardcoding 'if ch === ( push, if ch === ) check' three times instead of the pair table — readable but verbose.

Follow-up questions

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

Generate Parentheses (LeetCode 22) — generate all valid combinations.
Longest Valid Parentheses (LeetCode 32) — find the longest valid substring.
What if we add '<' and '>' as a fourth pair? (Just extend the table.)
Minimum Add to Make Parentheses Valid (LeetCode 921).

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 Valid Parentheses the canonical stack problem?

Because it's the smallest problem that exercises the stack's LIFO property meaningfully. Brackets close in reverse order of opening — exactly LIFO. IBM interviewers use it because it tests pattern recognition (do you reach for a stack?) in 5 minutes.

Can I solve this in O(1) extra space?

Not without modifying the input or restricting the alphabet. The stack of depth d (where d is the maximum nesting depth) is required because you must remember the type of each unmatched opener. For a single bracket type you could use a counter, but with three types the stack is unavoidable.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →