Command Palette

Search for a command to run...

Hectal
Problem 9.1 · Stack and Monotonic StackEasy

Valid Parentheses

PatternStack for Matching and Undo

What it teaches: The canonical stack problem: the most recent opener must close first.

Practise it on judges as “Valid Parentheses”.

The problem

Given a string s of the characters ()[]{}, return true if every bracket is closed by the same type, in the correct order.

Example 1

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

Example 2

Input: s = "(]"
Output: false

Example 3

Input: s = "([)]"
Output: false

Brackets cross instead of nesting.

Constraints

  • 1 ≤ s.length ≤ 10⁴
  • Only the six bracket characters

Pattern clues in the wording

  • → Brackets that must nest correctly
  • → The last opened must be the first closed

These clues point to Stack for Matching and Undo: Push openers and pop when the matching closer arrives; anything left over or mismatched is an error.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public boolean isValid(String s) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "()[]{}"
true
2
s = "(]"
false
3
s = "([)]"
false
4
s = "{[]}"
true

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: stack of expected closers · O(n)
1

Optimal: stack of expected closers

Time O(n) Space O(n)

For each opener, push the closer you expect. For each closer, the stack must be non-empty and its top must equal it. At the end, the stack must be empty.

▶ Dry run: Spotting a crossings = "([)]"
(
0
↑i
[
1
)
2
]
3

expected closers(stack)

)

Step 1/3'(' → expect ')'.

Approach 1
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> expect = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') expect.push(')');
            else if (c == '[') expect.push(']');
            else if (c == '{') expect.push('}');
            else if (expect.isEmpty() || expect.pop() != c) return false;
        }
        return expect.isEmpty();
    }
}

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Only closers (")")
  • Only openers ("((")
  • Odd length (can never be valid)

Mistakes people make

  • Not checking for an empty stack before popping.
  • Returning true without checking the stack is empty at the end.

Interview

Follow-up questions

What if only one bracket type exists?

How would you find the length of the longest valid substring?