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 Sam K., 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

More Stacks practice problems

See all Stacks problems →