20. Valid Parentheses

Q: What if the string is empty?

The stack will remain empty and the function returns true — an empty string is vacuously valid.

Q: Why use a map instead of a series of if-else checks?

A map scales cleanly to additional bracket types and eliminates repeated condition chains, which Broadcom interviewers reward as cleaner production code.

Q: Is O(n) space avoidable?

Not without extra constraints. The stack is necessary because you must remember the open-bracket order.

easyAsked at Broadcom

Determine whether a string of brackets is balanced. Broadcom asks this because stack-based parsing is the foundation of protocol-frame validation and command-line parsers inside embedded firmware — a real problem the team encounters when parsing network management commands.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

Glassdoor (2025-12)— Listed in Broadcom entry-level SWE interview reports as a stack fundamentals warm-up.
Blind (2025-09)— Broadcom new-grad threads mention bracket-matching as a first coding question before moving to graphs.

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

Explanation: Each open bracket is closed by a matching bracket in the correct order.

Example 2

Input

s = "(]"

Output

false

Explanation: The closing bracket ] does not match the opening bracket (.

Example 3

Input

s = "([)]"

Output

false

Explanation: Brackets are interleaved incorrectly — the innermost close doesn't match.

Approaches

1. Stack with match map

Push open brackets onto a stack. For each closing bracket, check the stack top for a match. Return true if the stack is empty at the end.

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

function isValid(s) {
  const stack = [];
  const match = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) {
      stack.push(ch);
    } else {
      if (stack.length === 0 || stack[stack.length - 1] !== match[ch]) return false;
      stack.pop();
    }
  }
  return stack.length === 0;
}

Tradeoff: O(n) time, O(n) space. Clean, idiomatic, and handles all edge cases. Broadcom interviewers appreciate the match-map pattern because it scales naturally to more bracket types.

Broadcom-specific tips

At Broadcom, connect this to protocol parsing: 'This is essentially what a frame parser does when validating nested TLV structures in networking protocols.' Mention that the stack approach generalises to validating XML/JSON config files used in Broadcom's VMware integration layers. Walk through the edge cases (empty string, single bracket, mismatched close before any open) before coding.

Common mistakes

Returning false when the stack is non-empty at the end — unclosed open brackets make the string invalid.
Forgetting to check that the stack is non-empty before popping — causes index-out-of-bounds.
Treating all closers the same without checking the type match.
Not handling the empty string — it should return true.

Follow-up questions

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

How would you extend this to validate HTML tags?
What if the input is a stream of characters arriving one at a time?
How would you report the position of the first mismatch rather than just true/false?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What if the string is empty?

The stack will remain empty and the function returns true — an empty string is vacuously valid.

Why use a map instead of a series of if-else checks?

A map scales cleanly to additional bracket types and eliminates repeated condition chains, which Broadcom interviewers reward as cleaner production code.

Is O(n) space avoidable?

Not without extra constraints. The stack is necessary because you must remember the open-bracket order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →