EasyStackStringUpdated Sep 2026

20. Valid Parentheses

Asked at Google, Meta, Amazon, Microsoft and 3 more

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

Stack

Companies

7

Problem

You get a string made only of the brackets (, ), {, }, [ and ]. Decide whether the string is valid.

A string is valid when every opening bracket is closed by the same kind of bracket, and brackets close in the right order — the most recently opened bracket must be the first one closed.

Same type, and in the right order

([])"([])" → valid: the inner pair closes first([)]"([)]" → invalid: ) arrives while [ is still open
Matching counts is not enough — the most recent open bracket has to close first.

Constraints

  • ●1 <= s.length <= 10^4
  • ●s contains only the characters ()[]{}

Examples

Example 1
Inputs = "()[]{}"
Outputtrue
WhyEach pair opens and closes immediately, and the types match.
Example 2
Inputs = "([])"
Outputtrue
WhyThe inner [ ] closes before the outer ( ), so the nesting is correct.
Example 3
Inputs = "([)]"
Outputfalse
WhyThe ) tries to close while [ is still open, so the order is wrong even though the counts match.
Example 4
Inputs = "(]"
Outputfalse
Why] does not match the open bracket (.

Asked At

7 companies
CompanyDifficulty
GoogleEasyView all Google questions →
MetaEasyView all Meta questions →
AmazonEasyView all Amazon questions →
MicrosoftEasyView all Microsoft questions →
WalmartEasyView all Walmart questions →
BloombergEasyView all Bloomberg questions →
LinkedInEasyView all LinkedIn questions →

How to Think About It

1

A stack is the natural data structure — push opening brackets, pop on closing brackets. The most recent unmatched opening bracket is always on top.

2

The key check: when you see a closing bracket, is the stack non-empty AND does the top match? If not, return false immediately.

3

Why stack works: brackets must close in LIFO order. The last opened bracket must be the first closed. That's exactly how a stack behaves.

4

Edge cases: odd-length strings are always invalid (early exit). Empty string is valid. Single bracket is invalid.

Optimal Approach

Step 1: Create a mapping of closing to opening brackets: {")":"(", "}":"{", "]":"["}.
Step 2: Iterate through the string.
Step 3: If character is an opening bracket, push it onto the stack.
Step 4: If character is a closing bracket:

  • If stack is empty → return false (no matching opener)
  • If stack top doesn't match → return false (wrong type)
  • Otherwise pop the matching opener
    Step 5: After processing all characters, stack must be empty (all openers were closed).

Time: O(n). Space: O(n) for the stack.

A stack remembers what is still open

after reading "(["([← topread ]top is [ → matchpop itafter reading "([]"(← topEmpty stack at the end → validAnything left over → invalid
Push every opening bracket. On a closing bracket, the top of the stack must be its partner.
ComplexityTime O(n)Space O(n)One pass over the string; the stack can hold every character in the worst case, e.g. "((((".

What Trips People Up in Real Interviews

1

Using a counter instead of a stack. A counter works for one type of bracket, but with multiple types, you need a stack to match the correct closing bracket.

2

Pushing closing brackets onto the stack. Only push opening brackets. When you see a closing bracket, check if it matches the top of the stack.

3

Forgetting to check if the stack is empty before popping. If the stack is empty when you see a closing bracket, it's invalid (no matching opener).

4

Not checking if the stack is empty at the end. If the stack has unmatched openers, it's invalid.

5

Replacing pairs iteratively instead of using a stack. Replacing "()" with "" repeatedly is O(n²) worst case and doesn't generalize to multiple bracket types. A stack handles all types in O(n).

Solution Code

O(n) time
def isValid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in mapping:
            if not stack or stack[-1] != mapping[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Valid Parentheses problem?

Given a string containing just the characters (, ), `{, }`, [ and ], determine if the input string is valid. An input string is valid if brackets are closed in the correct order. This problem tests your understanding of the stack data structure.

How do you solve Valid Parentheses?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Valid Parentheses?

Valid Parentheses is asked at Google, Meta, Amazon, Microsoft, Walmart, Bloomberg, LinkedIn. It is a easy difficulty problem.

What are common mistakes on Valid Parentheses?
  • Using a counter instead of a stack. A counter works for one type of bracket, but with multiple types, you need a stack to match the correct closing bracket.
  • Pushing closing brackets onto the stack. Only push opening brackets. When you see a closing bracket, check if it matches the top of the stack.
  • Forgetting to check if the stack is empty before popping. If the stack is empty when you see a closing bracket, it's invalid (no matching opener).
  • Not checking if the stack is empty at the end. If the stack has unmatched openers, it's invalid.
  • Replacing pairs iteratively instead of using a stack. Replacing "()" with "" repeatedly is `O(n²)` worst case and doesn't generalize to multiple bracket types. A stack handles all types in `O(n)`.