Skip to main content

2. Valid Parentheses

easyAsked at Electronic Arts

Validate that bracket characters in a string are properly matched and nested using stack-based parsing.

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

Problem

Given a string containing only the characters '(', ')', '{', '}', '[', ']', determine if the input string is valid. An input is valid if brackets are closed in the correct order and every opening bracket has a matching closing bracket.

Constraints

  • 1 <= s.length <= 10^4
  • s consists only of bracket characters

Examples

Example 1

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

Example 2

Input
s="(]"
Output
false

Approaches

1. Brute force replace

Repeatedly remove matching adjacent pairs until empty or stable.

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

Tradeoff:

2. Stack

Push openers; on a closer pop and compare against the expected match.

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

Tradeoff:

Electronic Arts-specific tips

EA likes to see explicit edge handling (empty string, single bracket) since gameplay parsers and asset-pipeline tools at EA shipped real bugs from missed edge cases.

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 Electronic Arts interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →