6  Valid Parentheses

Rank 4 · Pattern: stack of expected closings · Target: \(O(n)\) time

6.1 Problem definition

Given a string containing bracket characters, return whether every opening bracket is closed by the same bracket type in the correct nested order.

6.2 Clarifying questions

1. Which characters may appear in the input?
2. How should an empty string be classified?
3. Can the input string be null?

6.3 Sample answers

1. The input contains only (, ), [, ], {, and }.
2. An empty string is valid.
3. No. The input string is non-null.

6.4 Data structure: stack

The algorithm needs only push, pop, and an emptiness check.

Java

Deque<Character> with ArrayDeque supplies push, pop, and isEmpty. It is preferred to the legacy synchronized Stack class.

Python

A list is the usual stack: append pushes, pop removes the top, and an empty list is false in a condition.

Rust

A Vec<u8> is the stack. Because the contract permits only six ASCII bracket characters, iterating text.bytes() is both sufficient and direct.

6.5 Approach and invariant

Counting each bracket type is insufficient: ([)] has balanced counts but invalid nesting.

For each opener, push the closer it expects. For a closer, the stack must be nonempty and its top must equal that character. After the scan, the stack must be empty. Pushing the expected closer removes the need for a separate opener-to-closer map.

input:  ( [ ] { } )
stack:  )       '(' pushes expected ')'
        ) ]     '[' pushes expected ']'
        )       ']' matches and pops ']'
        ) }     '{' pushes expected '}'
        )       '}' matches and pops '}'
                ')' matches and pops ')' -> empty

Invariant: the stack, from bottom to top, contains the closing brackets required by the unmatched opening brackets encountered so far.

6.6 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class ValidParenthesesSolution {
    boolean balanced(String s) {
        Deque<Character> expectedClosings = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> expectedClosings.push(')');
                case '[' -> expectedClosings.push(']');
                case '{' -> expectedClosings.push('}');

                case ')', ']', '}' -> {
                    if (expectedClosings.isEmpty() || expectedClosings.pop() != c) {
                        return false;
                    }
                }

                default -> throw new IllegalArgumentException(
                    "Unexpected character: " + c
                );
            }
        }

        return expectedClosings.isEmpty();
    }

    @Test public void acceptsEmptyString() {
        assertTrue(balanced(""));
    }

    @Test public void acceptsSingleMatchingPair() {
        assertTrue(balanced("()"));
    }

    @Test public void acceptsAdjacentPairs() {
        assertTrue(balanced("()[]{}"));
    }

    @Test public void acceptsNestedPairs() {
        assertTrue(balanced("([]{})"));
    }

    @Test public void rejectsMismatchedPair() {
        assertFalse(balanced("(]"));
    }

    @Test public void rejectsWrongOrder() {
        assertFalse(balanced("([)]"));
    }

    @Test public void rejectsUnclosedBracket() {
        assertFalse(balanced("("));
    }

    @Test public void rejectsCloserWithoutOpener() {
        assertFalse(balanced("]"));
    }

    @Test(expected = IllegalArgumentException.class)
    public void rejectsUnexpectedCharacter() {
        balanced("(a)");
    }

    public static void main(String[] args) {
        JUnitCore.main("ValidParenthesesSolution");
    }
}

Python

import unittest


def is_valid(text):
    matching_opener = {")": "(", "]": "[", "}": "{"}
    stack = []

    for character in text:
        if character in "([{":
            stack.append(character)
        elif not stack or stack.pop() != matching_opener[character]:
            return False

    return not stack


class ValidParenthesesTests(unittest.TestCase):
    def test_accepts_empty_string(self):
        self.assertTrue(is_valid(""))

    def test_accepts_adjacent_pairs(self):
        self.assertTrue(is_valid("()[]{}"))

    def test_accepts_nested_pairs(self):
        self.assertTrue(is_valid("([]{})"))

    def test_rejects_mismatched_pair(self):
        self.assertFalse(is_valid("(]"))

    def test_rejects_wrong_order(self):
        self.assertFalse(is_valid("([)]"))

    def test_rejects_unclosed_bracket(self):
        self.assertFalse(is_valid("("))

    def test_rejects_closer_without_opener(self):
        self.assertFalse(is_valid("]"))


if __name__ == "__main__":
    unittest.main()

Rust

pub fn is_valid(text: &str) -> bool {
    let mut stack = Vec::new();

    for character in text.bytes() {
        match character {
            b'(' => stack.push(b')'),
            b'[' => stack.push(b']'),
            b'{' => stack.push(b'}'),
            closing => {
                if stack.pop() != Some(closing) {
                    return false;
                }
            }
        }
    }

    stack.is_empty()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn accepts_empty_string() {
        assert!(is_valid(""));
    }

    #[test]
    fn accepts_adjacent_pairs() {
        assert!(is_valid("()[]{}"));
    }

    #[test]
    fn accepts_nested_pairs() {
        assert!(is_valid("([]{})"));
    }

    #[test]
    fn rejects_mismatched_pair() {
        assert!(!is_valid("(]"));
    }

    #[test]
    fn rejects_wrong_order() {
        assert!(!is_valid("([)]"));
    }

    #[test]
    fn rejects_unclosed_bracket() {
        assert!(!is_valid("("));
    }

    #[test]
    fn rejects_closer_without_opener() {
        assert!(!is_valid("]"));
    }
}

Each version checks for an empty stack before accepting a closer, so an early closer returns false instead of causing a failed pop. The Java switch also names all three closer cases explicitly and throws for a character outside the stated input grammar.

6.7 High-value tests

Input	Expected	Purpose
""	true	empty
"()[]{}"	true	adjacent pairs
"([]{})"	true	nested and adjacent
"([)]"	false	wrong nesting
"]"	false	closer without opener
"("	false	leftover opener
"a"	throws	character outside the grammar (Java)

6.8 Complexity and correctness

Each character is pushed or popped at most once, so time is \(O(n)\). In the worst case all characters are openers, so space is \(O(n)\).

Any closer must match the most recent unmatched opener; that is exactly the stack top. A mismatch proves invalid ordering immediately. If every closer matches and the stack ends empty, every opener has exactly one correctly ordered closer.

6.9 If the interviewer pushes

• If arbitrary text is allowed, decide whether to ignore non-brackets or reject them. This Java version rejects them in the default branch.
• For only one bracket type, a counter suffices: never let it go negative and require zero at the end.
• For streaming input, the same algorithm works incrementally, but the final validity decision requires end-of-stream.

6.10 TDD interview script

Confirm that the input is non-null and contains only the six bracket characters, and that the empty string is valid. Then write this test list:

1. Empty string
2. One matching pair
3. Adjacent pairs
4. Nested pairs
5. Mismatched bracket type
6. Wrong nesting
7. Early closer
8. Unclosed opener
9. Unexpected character (Java)

Add one test per red–green–refactor cycle. Run the failure, implement only the next general rule, rerun the class, and refactor while green. Keep nested and adjacent examples separate so a failure immediately identifies whether sequencing or stack order is wrong. Assert only the returned boolean, not stack contents.

From book/src, run:

Java

./java/run.sh ValidParenthesesSolution

Python

./python/run.sh valid_parentheses_solution

Rust

./rust/run.sh valid_parentheses_solution

As the mismatch tests arrive, narrate why a stack is necessary: counts can prove that quantities match, but only the most recent unmatched opener can legally match the next closer.

6.10.1 Pseudocode

expectedClosings = empty stack

for each character c in s:
    if c is an opener:
        push its matching closer
    else if stack is empty or pop() is not c:
        return false

return stack is empty

The invariant is: from bottom to top, the stack contains exactly the closing brackets still required by the unmatched opening brackets seen so far.

6.10.2 TDD sequence

Step	Test code added	Production code added or changed
1. Empty grammar	acceptsEmptyString	Start with an empty stack and return whether it is empty after the scan.
2. One matching pair	acceptsSingleMatchingPair	Push the expected closer for ( and pop it when ) arrives.
3. Adjacent pairs	acceptsAdjacentPairs	Generalize opener handling for [] and {} and allow the emptied stack to be reused.
4. Nested pairs	acceptsNestedPairs	Use LIFO stack order so the innermost expected closer is matched first.
5. Wrong type	rejectsMismatchedPair	Compare each closer with the popped expected closer and return false on mismatch.
6. Wrong nesting	rejectsWrongOrder	Triangulate that balanced counts are insufficient and stack order controls validity.
7. Early closer	rejectsCloserWithoutOpener	Check isEmpty() before pop() and return false instead of throwing.
8. Missing closer	rejectsUnclosedBracket	Require the stack to be empty at end-of-input rather than returning true after the scan unconditionally.
9. Invalid character	rejectsUnexpectedCharacter (Java)	Make the six-character input grammar explicit with the switch default branch.

This order grows a tiny recognizer from the empty case, then uses boundary tests to drive both failure exits: an invalid closer during the scan and unmatched openers at the end.