Amazon · Coding 2 of 5

Valid Parentheses

Check whether a string of brackets opens and closes correctly.

EasyStackStringBest: O(n) time · O(n) space

Practice question: an editorial practice prompt, not a claim that Amazon asks this exact question. Interviews vary by role, level, team, and location.

Problem

Problem statement

Given a string s made only of the characters (, ), [, ], { and }, return true if the brackets are valid.

A string is valid when every opening bracket is closed by a bracket of the same type, brackets close in the correct order, and every closing bracket has a matching opening bracket before it.

Examples

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

Why: Nested pairs close from the inside out.

Example 3
Input
s = "([)]"
Output
false

Why: The ) arrives while [ is still the most recent open bracket.

Example 4
Input
s = "(("
Output
false

Why: Two brackets are never closed.

Constraints

  • 1 ≤ s.length ≤ 10⁴
  • s contains only the six bracket characters.
In the interview

How to answer it out loud

What it tests: Stack reasoning, invariant clarity, and careful handling of malformed input.

  1. 1
    Clarify

    Clarify the allowed characters and whether an empty string is valid.

  2. 2
    Implement

    Push opening brackets and require each closing bracket to match the top of the stack.

  3. 3
    Verify

    Test early closings, unmatched openings, mixed bracket types, and empty input; state O(n) time.

Approaches

From brute force to the best solution

ApproachIdeaTimeSpace
Repeated deletionRemove (), [] and {} pairs until nothing changes; valid if the string empties.O(n²)O(n)
StackBestPush opening brackets; each closing bracket must match the top of the stack.O(n)O(n)
Key insight

The most recently opened bracket is always the one that must close next — exactly the last-in, first-out order a stack gives you.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

def is_valid(s: str) -> bool:    pairs = {")": "(", "]": "[", "}": "{"}    stack = []    for ch in s:        if ch in pairs:                  # closing bracket            if not stack or stack[-1] != pairs[ch]:                return False            stack.pop()        else:                            # opening bracket            stack.append(ch)    return not stack                     # leftover openers mean invalid
Time
O(n)
Space
O(n)
Approach
Stack
Test cases

Edge cases to run before you say “done”

InputExpectedWhy it matters
s = ")"falseA closer on an empty stack — the classic crash.
s = "(("falseOpeners left over at the end.
s = "([)]"falseCounts match but the order is wrong.
Likely follow-ups

Answer the main question first, then take these on one at a time:

  • Can you report the first invalid position?
  • How would streaming input change the solution?
  • What if other characters are allowed?
Avoid these mistakes

Check your recording or written solution against this list:

  • Popping an empty stack
  • Checking only counts instead of order
  • Forgetting leftover opening brackets
Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Amazon questions or answers.

Amazon: software development interview topics ↗Amazon: Leadership Principles ↗
Official sources reviewed 20 September 2026.