Skip to main content

20. Valid Parentheses

easy

Decide whether a string of brackets is properly opened and closed in matching pairs. The canonical 'stack' introduction problem — a common screening warm-up.

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

Example 2

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

Example 3

Input
s = "(]"
Output
false

Example 4

Input
s = "([])"
Output
true

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

A counter (+1 for open, -1 for close) works only if there's a single bracket type.

Hint 2

The order matters: '(]' must be invalid, so a plain counter is not enough.

Hint 3

Use a stack. Push opens; on a close, pop and check the popped open matches the close type.

Solution approach

Reveal approach

Single-pass stack. For each character: if it's an opening bracket, push it; if it's a closing bracket, the stack must be non-empty AND the popped value must be the matching opener (use a tiny map: ')' -> '(', ']' -> '[', '}' -> '{'). Any mismatch or an empty pop returns false. At the end, the string is valid iff the stack is empty (no unclosed opens). O(n) time, O(n) extra space in the worst case (all opens).

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack

Related problems

Asked at

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

  • Amazon
  • Meta
  • Microsoft
  • Google
  • Bloomberg

More Strings practice problems

See all Strings problems →