Skip to main content

22. Valid Parentheses

easyAsked at Apple

Determine if bracket sequences are properly closed and ordered — Apple's Xcode editor and Swift compiler use this classic stack pattern daily to validate nested UI element trees, undo-stack integrity, and balanced XML attribute scopes in Interface Builder.

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

Problem

Given a string s containing only 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 bracket and in the correct order, and every close bracket has a corresponding open bracket.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'
  • Input string may contain mixed bracket types

Examples

Example 1

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

Example 2

Input
s = "(]"
Output
false

Explanation: Open paren cannot be closed by a square bracket

Approaches

1. Brute force (repeated replacement)

Repeatedly remove matching pairs until string is empty or no matches remain.

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

Tradeoff:

2. Stack

Push open brackets onto a stack; on each close bracket verify the top matches. Empty stack at end = valid.

Time
O(n)
Space
O(n)
function isValid(s) {
  const stack = [];
  const map = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (!map[ch]) {
      stack.push(ch);
    } else {
      if (stack.pop() !== map[ch]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff:

Apple-specific tips

Apple grades heavily on code cleanliness — interviewers have shipped Xcode and Instruments, so messy bracket-matching code stands out. Narrate why the stack mirrors how Xcode's syntax parser validates Swift bracket scopes. If you finish early, discuss how you'd extend this to catch mismatched XML/HTML tags in WebKit's DOM parser — Apple interviewers love applied follow-ups.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →