Valid Parentheses: Matching Brackets with a Stack

Problem

Determine whether a string s forms valid pairs of brackets. The string contains only (, ), {, }, [ and ]. Return true when all of these rules hold, or false otherwise:

1. Each opening bracket is paired with a closing bracket of its own type.
2. Pairs nest correctly: an inner pair finishes before the pair around it.
3. No closing bracket appears without a matching opening bracket.

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Example 4

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

Example 5

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

Constraints

• 1 <= s.length <= 10^4
• Every character in s is one of the six bracket characters above.

By the end of this lesson, you should be able to explain why counting brackets is insufficient, choose a stack, and write a solution that scans the string once.

Why counting is not enough

An equal number of opening and closing brackets is necessary, but it does not prove that the string is valid. For example, ")(" has one of each, but its first character closes a pair that never opened.

Even separate counts for each bracket type lose information. In "[(])", the totals balance and no type closes before its own opener, yet ] arrives while ( is still waiting to close. We need to remember the order of the unmatched openings.

One alternative is to repeatedly remove adjacent matching pairs: (), [], and {}. A valid string eventually becomes empty. However, deeply nested input such as "((()))" can require a new scan for each nesting level. With full-string scans and copies, this approach can take O(n²) time.

We can keep track of the nesting as we read instead.

The stack idea

A stack gives us three operations: push adds an item to the top, peek reads the top, and pop removes it. The most recently pushed item is the first one removed: last in, first out.

We could store opening brackets and check their partners later. Here, we store the expected closing brackets instead:

When a closing bracket arrives, it must equal the stack’s top. This lets us compare the characters directly.

Algorithm

1. Start with an empty stack.
2. For each opening bracket, push its matching closing bracket.
3. For each closing bracket, return false if the stack is empty or its top is different. Otherwise, pop the matching top.
4. After reading the entire string, return whether the stack is empty.

The final check matters: reaching the end without a mismatch does not mean all openings were closed.

Walkthrough: a valid string

Trace "[({})]". The stack below runs from bottom to top, so the rightmost entry is the next closing bracket we expect. The word “empty” means there are no entries.

We have consumed every character and the stack is empty, so the result is true.

Walkthrough: crossed pairs

Now trace "[(])":

Although ] appears lower in the stack, we cannot skip the top to reach it. Doing so would allow one pair to close through another unfinished pair. There is no need to read the last character once this mismatch is found.

Implementation

All three implementations follow the same steps. C# uses Stack<char>, Go uses a byte slice, and Python uses a list. Go can index bytes directly here because every allowed bracket is a single ASCII byte.

using System.Collections.Generic;

public class Solution
{
    public bool IsValid(string s)
    {
        var expected = new Stack<char>();

        foreach (char bracket in s)
        {
            if (bracket == '(')
                expected.Push(')');
            else if (bracket == '[')
                expected.Push(']');
            else if (bracket == '{')
                expected.Push('}');
            else
            {
                if (expected.Count == 0 || expected.Peek() != bracket)
                    return false;

                expected.Pop();
            }
        }

        return expected.Count == 0;
    }
}

func isValid(s string) bool {
	expected := []byte{}

	for i := 0; i < len(s); i++ {
		bracket := s[i]

		switch bracket {
		case '(':
			expected = append(expected, ')')
		case '[':
			expected = append(expected, ']')
		case '{':
			expected = append(expected, '}')
		default:
			if len(expected) == 0 || expected[len(expected)-1] != bracket {
				return false
			}

			expected = expected[:len(expected)-1]
		}
	}

	return len(expected) == 0
}

class Solution:
    def isValid(self, s: str) -> bool:
        closing = {"(": ")", "[": "]", "{": "}"}
        expected = []

        for bracket in s:
            if bracket in closing:
                expected.append(closing[bracket])
            else:
                if not expected or expected[-1] != bracket:
                    return False

                expected.pop()

        return not expected

Check for an empty stack before reading or removing its top. The short-circuit or/|| conditions stop that access when the stack is empty.

The implementations rely on the problem’s bracket-only input contract. They also return true for an empty string because nothing is unmatched, although the stated constraints exclude that input.

Why it works

After every successfully processed character, the stack holds one expected closing bracket for each unmatched opening, in opening order. Its top belongs to the most recent unmatched opening.

• An opening bracket adds one expectation and preserves that order.
• A matching closing bracket removes exactly the most recent expectation.
• A closing bracket with an empty stack has no opener. A closing bracket that differs from the top breaks the required nesting. Neither can be repaired by later characters, so returning false is correct.

At the end, an empty stack means every opening was closed correctly. A nonempty stack means some openings still need partners. This is why the final return checks the stack instead of always returning true.

Complexity

Let n be the length of the string.

• Time: O(n). Each character is read once, and each expected closing bracket is pushed once and popped at most once. Growable stack storage gives constant amortized time per push.
• Extra space: O(n) in the worst case. A string of opening brackets stores one expectation per character. More precisely, the stack holds at most the maximum number of simultaneously unmatched openings.

An odd-length string cannot be valid because each pair needs two characters. An early length check is an optional shortcut; the stack algorithm already rejects these strings correctly.

Common mistakes

• Checking only totals. Balanced counts still accept crossed pairs such as "[(])".
• Using a queue. A queue would close the oldest opening first, which fails for nested pairs of different types.
• Searching anywhere in the stack. Only the top is eligible to close; an earlier match cannot bypass an unfinished inner pair.
• Popping an empty stack. An input beginning with a closing bracket must return false safely.
• Forgetting the final empty check. An input such as "[](" has no mismatched closing bracket but still has an unfinished pair.

Try it yourself

Before running the code, predict the result for each input and identify the first mismatch or the contents left in the stack:

1. "{[()]}[]"
2. "}{"
3. "([]"
4. "{[}]"

Then write the solution without looking at the implementation. Explain what the stack stores, why a mismatch can return immediately, and why the final empty check is necessary. The same last-opened, first-closed pattern appears when processing nested expressions or tracking unfinished work during a depth-first traversal.