Skip to main content

20. Valid Parentheses

easyAsked at Glean

Glean uses this to test stack intuition — the same mechanism that powers balanced-query parsing in enterprise search engines where unclosed brackets in a structured query must be caught before execution.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2025-12)— Reported in Glean early-round phone screens as a standard stack problem.
  • Blind (2025-09)— Glean SWE candidates list Valid Parentheses as a common warm-up before harder system design questions.

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 bracket is immediately matched and closed in order.

Example 2

Input
s = "(]"
Output
false

Explanation: Opening '(' is closed by ']' which is the wrong type.

Example 3

Input
s = "([)]"
Output
false

Explanation: Brackets are interleaved — the inner pair closes before the outer pair.

Approaches

1. Stack with map

Push every opening bracket onto a stack. When you see a closing bracket, check if the top of the stack is the matching opener. At the end, the stack must be empty.

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: O(n) time and space. Clean and canonical — the only approach worth presenting in an interview unless specifically asked for alternatives.

Glean-specific tips

Connect this to Glean's domain: 'Parsing structured queries is one application — if a user types a boolean search with unclosed parentheses, you need to catch it before sending it to the index.' Glean interviewers appreciate candidates who tie algorithmic thinking to real search-system use cases.

Common mistakes

  • Not checking for an empty stack before popping — causes an out-of-bounds error on input like ']'.
  • Forgetting to verify the stack is empty at the end — '(' alone returns a non-empty stack but no closing bracket was ever seen.
  • Using a counter instead of a stack — works for a single bracket type but breaks when mixed types are interleaved.
  • Checking the wrong end of the stack — always peek at the top (last element), not the bottom.

Follow-up questions

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

  • Minimum Remove to Make Valid Parentheses (LC 1249) — remove the minimum number of brackets to make the string valid.
  • Generate Parentheses (LC 22) — enumerate all valid combinations of n pairs.
  • What if the string can contain non-bracket characters? (Ignore them and validate only brackets.)

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 does a counter approach fail for mixed brackets?

A counter only tracks balance, not type. '([)]' has balance 0 at the end but is invalid because brackets interleave. The stack preserves type information at every nesting level.

What is the space complexity in the best case?

O(1) if the string has no opening brackets (all closings fail immediately). But worst case is O(n) — e.g., n/2 opening brackets followed by n/2 closers all go on the stack.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →