Skip to main content

20. Valid Parentheses

easyAsked at Gusto

Check whether a string of brackets is properly nested and closed. Gusto asks this to test stack intuition and clean code — they want to see a minimal bracket map and early exits, not a sprawling switch statement.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-10)— Candidates report this as a phone-screen problem at Gusto with a follow-up on edge cases.
  • Blind (2025-09)— Mentioned in Gusto SWE prep threads as an early-round stack problem used to assess code clarity.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: open brackets are closed by the same type of bracket, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only: '()[]{}'.

Examples

Example 1

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

Explanation: All three pairs are opened and closed independently and in order.

Example 2

Input
s = "([)]"
Output
false

Explanation: The brackets interleave incorrectly — '[' is closed by ')' before ']' appears.

Example 3

Input
s = "{[]}"
Output
true

Explanation: Nested correctly: '[' is closed before '}'.

Approaches

1. Stack with a closing-bracket map

Push open brackets onto a stack. When a closing bracket is seen, check if the top of the stack is its matching open bracket. At the end, the stack must be empty.

Time
O(n)
Space
O(n)
function isValid(s) {
  const match = { ')': '(', '}': '{', ']': '[' };
  const stack = [];
  for (const ch of s) {
    if (match[ch]) {
      // closing bracket — top of stack must be its partner
      if (stack.pop() !== match[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

Tradeoff: Single pass, linear time and space. The map approach keeps the bracket pairing data in one place — easy to extend if you add new bracket types.

Gusto-specific tips

Gusto interviewers specifically look for candidates who handle the empty-stack case before calling pop() — returning false when a closing bracket arrives with nothing on the stack. Mention you'd test the empty string, a string of only closing brackets, and a correct deeply-nested case. Avoid a long if/else chain for bracket types; the map pattern is cleaner and they'll notice.

Common mistakes

  • Not checking that the stack is empty at the end — a string like '(((' passes all the loop checks but is invalid.
  • Calling stack.pop() without checking if the stack is empty first — in some languages this crashes; in JS it returns undefined which happens to work but is fragile.
  • Using a separate variable for the top element instead of popping directly — causes bugs when you forget to pop.
  • Checking only that each close bracket has any open bracket on the stack rather than the correct matching open bracket.

Follow-up questions

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

  • How would you handle extra whitespace or ignore non-bracket characters?
  • Extend the solution to return the index of the first invalid character.
  • How would you test this? What are the minimal edge-case categories?

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 a map from closing to opening bracket rather than the reverse?

When processing a closing bracket, you want to immediately look up what its matching open bracket should be. Keying by the closing bracket makes that a direct O(1) lookup.

What does an empty stack at a closing bracket mean?

There's no open bracket waiting to be matched — the string is invalid. You must return false before popping.

Is there an O(1)-space solution?

Not in general for mixed bracket types, since you need to remember open-bracket order. If only one bracket type is used, a counter suffices.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →