Valid Parentheses

The problem

You are given a string text made only of the six bracket characters (, ), [, ], { and }. Return true if every bracket is closed correctly, and false otherwise.

Closed correctly means three things. Every open bracket is closed by the same kind of bracket. Brackets close in the right order: the one opened last closes first. And no closing bracket appears without an open one before it.

Example 1

Input: text = "({[]})()"

Output: true

The square pair sits inside the curly pair, which sits inside the round pair. Then one more round pair follows.

text

(0{1[2]3}4)5(6)7

Example 2

Input: text = "[(])"

Output: false

The “]” arrives while “(” is still open. The brackets cross instead of nesting.

Example 3

Input: text = "(("

Output: false

Both brackets are opened and never closed.

Constraints

• 1 ≤ n ≤ 10,000, where n is the length of text
• text holds only the characters ()[]{}.

Clarifying questions

Can there be other characters, like letters?

No. Only the six bracket characters.

Is "([])" valid?

Yes. Brackets may nest inside other kinds of brackets.

Is ")(" valid?

No. A closing bracket needs an open one before it, not after.

Does an odd length mean false?

Yes. Every bracket needs a partner, so a valid string has an even length.

Spot the pattern

Each closing bracket must match the most recent open bracket that is still waiting. “Most recent first” is exactly how a stack works: the last thing you put on top is the first thing you take off. So push every open bracket, and let every closing bracket check the top.

Solutions

Remove pairsO(n²)StackO(n)

Show all

This problem has two approaches. There is no useful step between them.

Remove pairs O(n²)

The idea

A valid string, if it is not empty, always has a matched pair standing side by side, like “[]”. Remove it and the rest is still valid. So keep removing every “()”, “[]” and “”, pass after pass.

If the string ends up empty, every bracket had a partner. If a pass removes nothing and something is left, that leftover can never be matched.

Walkthrough

text

(0{1[2]3}4)5(6)7

1. while True:
2. reduced = text.replace("()", "").replace("[]", "").replace("{}", "")
3. if reduced == text: break
4. text = reduced
5. return text == ""

A valid string always has a matching pair side by side, like "[]". Remove such pairs again and again.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Remove pairs: a valid string always has a matched pair side by side.
    // Up to n / 2 passes, each scanning the string: O(n^2) time, O(n) memory.
    public boolean isValid(String text) {
        while (true) {
            String reduced = text.replace("()", "").replace("[]", "").replace("{}", "");
            // No pair was removed, so nothing more can be removed.
            if (reduced.equals(text)) break;
            text = reduced;
        }
        return text.isEmpty();
    }
}

Big O

Time O(n²)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line is one pass. It is one line, but it is not one step: each replace reads the whole string, so one pass costs about 3 × (current length) steps. The while loop repeats the pass.

   1. while True:
   2. reduced = text.replace("()", "").replace("[]", "").replace("{}", "")
   3. if reduced == text: break
   4. text = reduced
   5. return text == ""

2. 2 Count the runs on Example 1

   Example 1 starts with 8 characters. Pass 1 reads the 8 characters three times and leaves “()”. Pass 2 reads 2 characters three times and leaves “”. Pass 3 finds nothing to change.

   24 + 6 + 0 = 30 characters read.

   pass	1	2	3
   length at start	8	2	0
   characters scanned	3 × 8 = 24	3 × 2 = 6	0

3. 3 Write the count for any n

   In the worst case, like “((((…))))”, each pass removes only one pair, so the length shrinks by just 2 each time. That means about n / 2 passes, of length n, then n − 2, and so on:

   3 × (n + (n − 2) + (n − 4) + … + 2) ≈ 3 × n² / 4

   Check it with Example 1: three of its pairs sit side by side at the start, so it shrinks much faster than the worst case. 30 is well below 3 × 64 / 4 = 48.

4. 4 Keep only the part that grows fastest

   Drop the ¾. A fixed factor does not change how fast the count grows. When n doubles, the work grows 4 times. What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   Each pass builds a new string reduced, up to n characters long. So the space is O(n).

   reduced (up to n characters)

Stack O(n)

The idea

Read the string once, left to right, with a stack.

• An open bracket goes on top of the stack. It waits there for its partner.
• A closing bracket must match the bracket on top. If the stack is empty, or the top is a different kind, the string is invalid. If it matches, pop the top: that pair is done.

At the end, the stack must be empty. Anything still on it was opened and never closed.

Why it is correct: the top of the stack is always the most recent open bracket that has not been closed yet, and that is the only bracket a closing bracket is allowed to match.

Walkthrough

text

(0{1[2]3}4)5(6)7

stack top →

empty

1. stack = []
2. for bracket in text:
3. if bracket in ")]}":
4. if not stack or stack[-1] != pair[bracket]:
5. return False
6. stack.pop()
7. else: stack.append(bracket)
8. return not stack

Read left to right. Push each opening bracket. A closing bracket must match the most recent open one, which is the top of the stack.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Stack: the latest open bracket must be the first one to close.
    // One pass with O(1) work per bracket: O(n) time, O(n) memory.
    public boolean isValid(String text) {
        Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char bracket : text.toCharArray()) {
            if (pair.containsKey(bracket)) {
                // A close needs its own kind of open on top, not just any open.
                if (stack.isEmpty() || stack.peek() != pair.get(bracket)) return false;
                stack.pop();
            } else {
                stack.push(bracket);
            }
        }
        // Anything left on the stack was opened and never closed.
        return stack.isEmpty();
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one push, or one check and one pop. A push, a pop and a look at the top each take one step, so each run is 1 step. There is one loop.

   1. stack = []
   2. for bracket in text:
   3. if bracket in ")]}":
   4. if not stack or stack[-1] != pair[bracket]:
   5. return False
   6. stack.pop()
   7. else: stack.append(bracket)
   8. return not stack

2. 2 Count the runs on Example 1

   Example 1 has 8 characters. The loop runs once for each: 4 pushes and 4 pops.

   8 runs.

   bracket	0	1	2	3	4	5	6	7
   char	(	{	[	]	}	)	(	)
   action	push	push	push	pop	pop	pop	push	pop

3. 3 Write the count for any n

   n times

   Check it with Example 1: 8 characters, 8 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   In the worst case every character is an open bracket, like “((((”. Then all n go on the stack. The space is O(n).

   stack (up to n brackets)bracket

Common mistake

Forgetting the empty stack

Two checks are easy to miss. A closing bracket on an empty stack, like the first character of “)(”, must return false before you look at the top. And a string like “((” passes every check inside the loop, so the final return must check that the stack is empty.

Tested at the limits

2,000 random strings of brackets: half balanced, some of those broken by one change, the rest random. The remove pairs and the stack gave the same answer every time.

Largest inputs	Result
10,000 brackets (the most allowed): 5,000 opens, then their 5,000 closes, the deepest nesting. Also with the last close the wrong kind. Stack.	Under 0.001 s, and about 0.04 MB of extra memory: the stack holds 5,000 brackets, which is the O(n) space.
10,000 brackets, same nesting. Remove pairs.	0.06 s for 5,000 passes. Each pass removes only the one pair in the middle.