Skip to main content

20. Valid Parentheses

easyAsked at Hugging Face

Determine whether a string of brackets is valid. Hugging Face uses this to probe stack intuition — the same LIFO discipline that governs recursive transformer decoder calls and nested tokenization schemas in production ML systems.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2025-12)— Listed in Hugging Face early-round coding reports as a standard stack warm-up.
  • Blind (2025-09)— Hugging Face interview threads reference Valid Parentheses as a common phone screen problem for junior to mid-level roles.

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 immediately closed by its matching type.

Example 2

Input
s = "(]"
Output
false

Explanation: The open parenthesis is closed by a square bracket — type mismatch.

Example 3

Input
s = "([])"
Output
true

Explanation: Nested brackets that close in the correct order.

Approaches

1. Stack with map

Push every open bracket onto a stack. For each closing bracket, check that it matches the top of the stack. If the stack is empty at the end, the string is valid.

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

Tradeoff: Clean and canonical. The closing-bracket map avoids a chain of if/else. Always check stack.length > 0 before popping to handle leading close brackets.

Hugging Face-specific tips

Hugging Face engineers appreciate when you connect the problem to real-world parsing: 'A stack is the natural data structure for any grammar with nested scopes — the same way an ML config parser validates YAML nesting or a tokenizer validates paired special tokens.' State the invariant explicitly: at every point in the loop, the stack holds all unmatched open brackets seen so far.

Common mistakes

  • Forgetting to check that the stack is empty at the end — a string like '(((' passes all per-character checks but is invalid.
  • Popping from an empty stack on a closing bracket — always guard with stack.length > 0 first.
  • Storing closing brackets instead of opening brackets, which inverts the matching logic.
  • Not handling the empty string — it is valid (return true immediately).

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Minimum Remove to Make Valid Parentheses (LC 1249) — remove the fewest characters to make the string valid.
  • Longest Valid Parentheses (LC 32) — find the longest valid substring.
  • How would you extend this to validate arbitrary paired tokens in a custom DSL or config file format?

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 use a map for matching instead of if/else?

The map makes it trivial to extend to new bracket types and keeps the closing-bracket check to a single lookup rather than three comparisons.

Can I solve this without a stack?

For strictly '()' only, a counter works. For multiple bracket types you need a stack to track which type was opened last.

What is the space complexity in the worst case?

O(n) — a string of all open brackets pushes every character onto the stack.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →