Skip to main content

20. Valid Parentheses

easyAsked at Elastic

Determine whether a string of brackets is balanced. Elastic reaches for this in phone screens because the stack-based parse pattern is directly analogous to query-string and JSON document validation that Elasticsearch performs on every indexed document.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-12)— Elastic phone-screen reports frequently mention stack-based parsing problems as a first warm-up question.
  • Blind (2025-09)— Multiple Elastic SWE threads confirm bracket validation appears in the first coding round alongside hash-map 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 are closed by the same type of brackets, open brackets are 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 opening bracket is closed correctly and in order.

Example 2

Input
s = "(]"
Output
false

Explanation: The opening parenthesis is closed by a square bracket — mismatched types.

Example 3

Input
s = "([)]"
Output
false

Explanation: The brackets are not closed in the correct order.

Approaches

1. Stack with map

Push every open bracket onto a stack. When a closing bracket is encountered, pop from the stack and check that the popped bracket is the matching open type. 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: Single pass, O(n) time and O(n) space. The map eliminates the need for if-else chains and makes it trivial to extend to new bracket types — a clean pattern for production parsers.

Elastic-specific tips

After solving, Elastic interviewers often ask how this generalizes to validating Elasticsearch query DSL — a JSON structure with nested must/should/filter clauses. Mention that a recursive descent parser or a stack-based approach handles nested structures cleanly. Also note that the map-keyed-by-close-bracket pattern makes adding new bracket types a single-line change, which demonstrates extensibility thinking.

Common mistakes

  • Returning true when the stack is non-empty at the end — all open brackets must be consumed.
  • Not handling the empty-stack case before popping — an extra closing bracket on an empty stack should return false immediately.
  • Checking the match map with open brackets instead of close brackets — invert the map so closing brackets are the keys.
  • Assuming the string contains only one type of bracket — always test with mixed types.

Follow-up questions

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

  • Minimum number of parentheses to add to make a string valid (LC 921).
  • Longest valid parentheses substring (LC 32) — harder variant using dynamic programming or stack.
  • How would you extend this to validate Elasticsearch query JSON with required field keys?

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 stack instead of a counter?

A single counter works only for one bracket type. A stack preserves the order of open brackets, which is necessary to match them correctly when multiple types are interleaved.

What is the space complexity in the worst case?

O(n) — a string like '(((((' pushes all n characters onto the stack before any matching occurs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →