Skip to main content

20. Valid Parentheses

easy

Decide whether a string of brackets is properly opened and closed. The textbook 'why do we need a stack' problem — and the warm-up that interviewers use to ramp into harder follow-ups.

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

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; 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

Example 2

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

Example 3

Input
s = "(]"
Output
false

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

When you see a closing bracket, you need to remember the most recent unmatched opener. That's a stack.

Hint 2

Map each closing char to its matching opener.

Hint 3

Push openers as you scan. On a closer, check that the top of the stack is its matching opener; pop. At end, the stack must be empty.

Hint 4

Edge case: an odd-length input can never be valid — quick early exit.

Solution approach

Reveal approach

Single pass with a stack. Pre-build a map from closing bracket to matching opener: ')' -> '(', ']' -> '[', '}' -> '{'. Scan the string: if the char is an opener, push it. If it's a closer, the stack must be non-empty and its top must equal the matching opener; otherwise return false. After the scan, return true iff the stack is empty. O(n) time, O(n) space worst case (a string of all openers). Optional early exit: odd-length strings cannot be valid.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Valid Parentheses and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →