Start practising

Valid Parentheses

Easy Stack Stack Basics Original on LeetCode

Valid Parentheses is a easy stack problem solved with the stack basics pattern. The best approach, optimal (stack), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from brute force (remove matched pairs) up.

Problem

Given a string of brackets ()[]{}, decide whether it is valid: every opening bracket is closed by the same type, and brackets close in the correct order.

Examples

Example 1

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

Example 2

Input
s = "([)]"
Output
false
Why
The ] arrives while ( is still open.

Example 3

Input
s = "(("
Output
false
Why
Brackets left open at the end.

Constraints

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

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (remove matched pairs)O(n²)O(n)
Optimal (stack)O(n)O(n)

1Brute force (remove matched pairs)

TimeO(n²)
SpaceO(n)

Repeatedly delete adjacent pairs (), [] and {} until nothing changes. The string is valid if it ends up empty.

  1. Loop: replace every (), [], {} with nothing.
  2. Stop when the length stops changing.
Java
class Solution {
    public boolean isValid(String s) {
        int prev = -1;
        while (prev != s.length()) {
            prev = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        }
        return s.isEmpty();
    }
}

2Optimal (stack)

TimeO(n)
SpaceO(n)

Push each opening bracket. For a closing bracket the top of the stack must be its matching opener; pop it. At the end the stack must be empty.

  1. For '(' push ')', and likewise for '[' and '{' (push the expected closer).
  2. For a closer: if the stack is empty or pop() != c, return false.
  3. Return stack.isEmpty().
Java
class Solution {
    public boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') st.push(')');
            else if (c == '[') st.push(']');
            else if (c == '{') st.push('}');
            else if (st.isEmpty() || st.pop() != c) return false;
        }
        return st.isEmpty();
    }
}

Edge cases to test

  • A closing bracket with an empty stack
  • Unclosed brackets left at the end
  • Odd length (always false)

Hints

Hint 1

The most recent unclosed bracket must be closed first.

FAQ

What is the best time complexity for Valid Parentheses?

Optimal (stack) runs in O(n) time and O(n) extra space.

Which pattern does Valid Parentheses use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Baseball Game, Asteroid Collision, Min Stack.

Is there a brute force solution for Valid Parentheses?

Yes. Brute force (remove matched pairs) takes O(n²) time and O(n) space. Repeatedly delete adjacent pairs (), [] and {} until nothing changes.

Which edge cases should I test for Valid Parentheses?

A closing bracket with an empty stack; Unclosed brackets left at the end; Odd length (always false).