Valid Parentheses:Push Opens, Pop on a Match

A billing config interpolator mixed (), {}, and [] in a JSON-ish template — sections, maps, and filters. The intern counted opens and closes of each type. Staging’s ()[]{} shipped clean. A generated filter ([)] had one of each pair, the counter returned valid, and the parser died: the first ) was sitting on a [.

Valid Parentheses asks whether every open is closed by the matching type, in the right order. A per-type count uses that and still accepts ([)]. Matching is order, not totals.

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about the unmatched opens from the left so a close is a pop, not a recount.

The problem

Given a string s of brackets (), {}, and [] only, return whether it is valid: every open is closed by the same type, and a close matches the most recent unmatched open. The empty string is valid.

s = "()"      →  true
s = "()[]{}"  →  true
s = "(]"      →  false
s = "([)]"    →  false
s = "{[]}"    →  true
s = ""        →  true

Note: Enumerating every valid string of this length is a different problem — Generate Parentheses. This prompt asks you to check one string.

A backward scan is the honest brute force

A running count per type is not a brute force — ([)] balances each family and is still invalid. The honest quadratic check does not count: for each close, scan backward for the nearest unmatched character, which must be the matching open, then mark both used. Leftover unmatched opens fail.

boolean isValidScan(String s) {
    int n = s.length();
    boolean[] matched = new boolean[n];
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            continue;
        }
        int j = i - 1;
        while (j >= 0 && matched[j]) {
            j--;
        }
        if (j < 0) {
            return false;
        }
        char o = s.charAt(j);
        if ((c == ')' && o != '(')
                || (c == '}' && o != '{')
                || (c == ']' && o != '[')) {
            return false;
        }
        matched[j] = true;
        matched[i] = true;
    }
    for (boolean m : matched) {
        if (!m) {
            return false;
        }
    }
    return true;
}

At n = 20 the leftward scan is a rounding error. At n in the tens of thousands you paid a nested walk for a question whose nearest unmatched open is already the top of a stack.

Push opens, pop on a match

Walk left to right. Odd length cannot pair — return false before you allocate.

• Open: push.
• Close: the stack must be non-empty and peek must match that close; then pop.
• End of string: the stack is empty. Leftover opens or a mismatch → false.

The nearest unmatched open is no longer a scan. It is the top.

s = "([{}])"

(     push            stack: (
[     push            stack: ( [
{     push            stack: ( [ {
}     peek {  match   pop     stack: ( [
]     peek [  match   pop     stack: (
)     peek (  match   pop     stack: empty
end   empty  →  true

s = "([)]"

(     push            stack: (
[     push            stack: ( [
)     peek [  ≠ (     →  false

The Java is that walk:

boolean isValid(String s) {
    int n = s.length();
    if (n % 2 != 0) {
        return false;
    }
    Deque<Character> open = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            open.push(c);
            continue;
        }
        if (open.isEmpty()) {
            return false;
        }
        char top = open.peek();
        if ((c == ')' && top != '(')
                || (c == '}' && top != '{')
                || (c == ']' && top != '[')) {
            return false;
        }
        open.pop();
    }
    return open.isEmpty();
}

Time is O(n) — one pass, one push or pop per character. Space is O(n) for unmatched opens (worst case the string is all opens). Empty string: length 0, even, the loop never runs, the stack is empty, you return true without a special case.

Note: A close on an empty stack is a pop you must not do. Return false; do not call pop. Leftover opens at the end ("((") fail the empty check. ()[] is two sequential pairs; ([)] is a crossed pair — the stack is how you tell them apart.

What interviewers usually poke next

• Only (). Then a single counter is enough; the stack is overkill, and you should say why ([)] forced the stack in the three-type prompt.
• Count-only for (). Nested (()()) works with +1/−1. You never needed types, and you never needed a stack.
• Unicode / extra bracket types. Map each close to its open instead of three ifs. The walk does not change.
• Streaming. You cannot reread s. The stack still works in one pass; you only hold unmatched opens.
• Generate every valid string. That is Generate Parentheses, not a checker.

You are done with this problem when you can reject ([)] without a count, refuse to pop an empty stack, and require empty at the end.