SyntaxPilot
Courses/DSA and Coding Problems/Lesson 26
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 26 of 90

Stacks: valid parentheses

queued

These are the notes for DSA episode 26, the first problem of the stack block. Given a string of brackets, decide whether every bracket is closed by its own type, in the right order, with nothing left open. The obvious way keeps rubbing out (), [] and {} pairs until nothing changes: correct, but O(n²), and it times out on 2 lakh characters. Counting opens and closes is fast but wrong ("([)]" passes). The fix is the stack: push every opening bracket, and on every closing bracket pop the top and check the type. O(n) time, O(n) space. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A maths homework sum: { [ (2+3) × 4 ] − 1 }. You solve it inside out: the round bracket closes first, then the square one, then the curly one. A typo like { [ (2+3 ] × 4 ) − 1 } closes the square bracket while the round one is still open: the brackets cross and the sum makes no sense. A teacher spots it with one rule: the bracket opened most recently must be the next one to close.

In the homework In the code
A bracket you open an opening character (, [, {
A bracket you close a closing character ), ], }
"Which bracket is still open, most recent first?" the stack, top first
Close the latest one first pop the top and compare
Nothing left open at the end the stack is empty

Problem statement

Given a string s containing only the characters ( ) [ ] { }, return true if it is valid:

  1. every closing bracket is closed by the same type of opening bracket,
  2. brackets close in the correct order,
  3. every opening bracket is closed (nothing left open).
"()[]{}" → true      "([{}])" → true
"(]"     → false     "([)]"   → false

Edge cases: "" (empty: valid, nothing is wrong with it), "((" (left open), "))" (a close with nothing open).

Brute force: rub out matching pairs

Any opening bracket sitting right next to its own closing bracket is a finished pair: delete it. Deleting one pair can bring a new pair together ("([])" → "()" → ""), so repeat until a full pass changes nothing. Empty at the end means valid.

public class Main {
    static boolean bruteValid(String s) {
        while (true) {
            String t = s.replace("()", "")
                        .replace("[]", "")
                        .replace("{}", "");
            if (t.equals(s)) return s.isEmpty();
            s = t;
        }
    }
    public static void main(String[] args) {
        System.out.println(bruteValid("()[]{}"));
        System.out.println(bruteValid("([{}])"));
        System.out.println(bruteValid("(]"));
        System.out.println(bruteValid("([)]"));
    }
}

Output:

true
true
false
false

The big input: 2 lakh characters

        int n = 100000;
        String s = "(".repeat(n) + ")".repeat(n);

One lakh ( followed by one lakh ): valid and deeply nested. The brute force gets Time Limit Exceeded. With n = 10000 (20,000 characters) it already takes about 330 ms.

Why the brute force fails

In the nested string only the middle pair touches, so each pass removes one pair: n/2 passes. Each pass builds a brand-new string of up to n characters. Total ≈ n²/4 character copies:

Length Work
1,000 2.5 lakh steps
20,000 10 crore
2 lakh 10¹⁰: TLE

It keeps re-reading brackets it has already understood. We want one left-to-right pass.

A fast but wrong shortcut: counting

    static boolean countValid(String s) {
        int open = 0;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') open++;
            else open--;
            if (open < 0) return false;
        }
        return open == 0;
    }

countValid("([{}])"), countValid("(]"), countValid("([)]") print true, true, true. Two are wrong. A counter knows how many brackets are open, but forgets which ones and in what order. (Counting does work when there is only one type of bracket.)

The key insight: the open brackets are a stack

The stack, from zero

A pile of clean plates at a wedding buffet: you only ever touch the top plate.

At the buffet In code Meaning
A pile of plates stack a collection where you add and remove only at one end, the top
Put a plate on top push(x) add x on top
Take the top plate pop() remove the top item and return it
Look at the top plate peek() read the top item without removing it
The last plate put down is the first taken LIFO last in, first out

The teacher's rule "last opened, first closed" is LIFO. So keep the open brackets on a stack; the top is always the bracket that must close next.

  1. Opening bracket → push it.
  2. Closing bracket and the stack is empty → false (nothing to close).
  3. Otherwise pop the top: it must be the same type, else false.
  4. End of string → valid only if the stack is empty.

Dry run: "{[()]}"

i char action stack (top first)
0 { push {
1 [ push [ {
2 ( push ( [ {
3 ) pop (: match [ {
4 ] pop [: match {
5 } pop {: match empty
end stack empty → true

Dry run: "([)]"

i char action stack (top first)
0 ( push (
1 [ push [ (
2 ) pop [: not ( → false

The optimal solution in Java

In Java the recommended stack is ArrayDeque (from java.util). A deque (said "deck") is a double-ended queue: you can add and remove at both ends; its push, pop and peek work on the front, so it behaves as a stack. (The old Stack class works too, but it is synchronized and slower.) Collections hold objects, so the type is Deque<Character>; Java converts char ↔ Character automatically (autoboxing).

import java.util.*;

public class Main {
    static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(isValid("()[]{}"));
        System.out.println(isValid("([{}])"));
        System.out.println(isValid("(]"));
        System.out.println(isValid("([)]"));
        System.out.println(isValid(""));
        System.out.println(isValid("(("));
        System.out.println(isValid("))"));
    }
}

Output:

true
true
false
false
true
false
false

On the 2 lakh character input it printed 200000 chars: true, 16 ms. Every character is pushed once or popped once.

Small speed-up: a valid string has even length, so if (s.length() % 2 == 1) return false; at the top skips odd inputs immediately.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

bool isValid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return st.empty();
}

int main() {
    for (string s : {"()[]{}", "([{}])", "(]", "([)]", "", "((", "))"})
        cout << boolalpha << isValid(s) << "\n";
}

Output: true true false false true false false (one per line). Note that in C++ pop() returns nothing: read top() first, then pop(). Calling top() on an empty std::stack is undefined behaviour, so the empty() check matters even more.

The same solution in Python

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        else:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

for s in ["()[]{}", "([{}])", "(]", "([)]", "", "((", "))"]:
    print(is_valid(s))

Output: True True False False True False False (one per line). A Python list is a stack: append is push, pop() is pop, stack[-1] is peek.

Three real bugs

Bug 1: pop() without checking isEmpty()

isValid("()");   // true
isValid(")(");   // crash
true
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
    at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:592)
    at Main.isValid(Main.java:10)
    at Main.main(Main.java:20)

A closing bracket arrived with nothing on the stack. ArrayDeque.pop() throws when empty. Fix: if (stack.isEmpty()) return false; before popping.

Bug 2: return true; at the end

isValid("([])") → true, and isValid("((") → true. Wrong! Nothing failed inside the loop, so the code fell through to true. Leftover openers only show up at the end. Fix: return stack.isEmpty();.

Bug 3: Deque<char>

Main.java:5: error: unexpected type
        Deque<char> stack = new ArrayDeque<>();
              ^
  required: reference
  found:    char
1 error

Generic collections hold objects (references), not primitives. Use the wrapper class Character.

Complexity

Approach Time Extra space 2 lakh characters
Rub out pairs with replace O(n²) O(n) per copy Time Limit Exceeded
Count opens and closes O(n) O(1) fast but wrong for 2+ types
Stack O(n) O(n) (all openers, worst case) 16 ms

Common mistakes

Mistake What you see Why Fix
pop() without isEmpty() java.util.NoSuchElementException a close with nothing open if (stack.isEmpty()) return false;
return true; at the end isValid("((") → true leftover openers never checked return stack.isEmpty();
Deque<char> error: unexpected type collections hold objects Deque<Character>
Counting instead of a stack countValid("([)]") → true forgets type and order use a stack
C++: char top = st.pop(); error: void value not ignored as it ought to be std::stack::pop() returns void top() then pop()
Comparing the close to itself everything false pushing the close instead of the open push openers only, compare with the matching opener

Mini project: a bracket checker for code

Write checkCode(String code) that checks the brackets of a line of real Java code, but ignores brackets inside string and char literals ("{", ')').

    static boolean checkCode(String code) {
        Deque<Character> st = new ArrayDeque<>();
        char quote = 0;
        for (int i = 0; i < code.length(); i++) {
            char c = code.charAt(i);
            if (quote != 0) { if (c == '\\') i++; else if (c == quote) quote = 0; continue; }
            if (c == '"' || c == '\'') quote = c;
            else if (c == '(' || c == '[' || c == '{') st.push(c);
            else if (c == ')' || c == ']' || c == '}') {
                if (st.isEmpty()) return false;
                char t = st.pop();
                if ((c == ')' && t != '(') || (c == ']' && t != '[') || (c == '}' && t != '{')) return false;
            }
        }
        return st.isEmpty();
    }

checkCode("if (a[0] == ')') { print(\"{\"); }") → true; checkCode("int x = (1 + 2];") → false. This is the core of what your editor does when it highlights a matching bracket.

Practice

  1. Minimum adds to make a string of ( and ) valid.
Solution

One bracket type, so a counter is enough. open counts unmatched (; a ) with no open ( needs one added.

    static int minAddToMakeValid(String s) {
        int open = 0, add = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (open > 0) open--;
            else add++;
        }
        return add + open;
    }

"())" → 1, "(((" → 3.

  1. Longest valid parentheses substring (hard).
Solution

Push indices. Keep the index just before the current valid run at the bottom (start with -1).

    static int longestValid(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1);
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') st.push(i);
            else {
                st.pop();
                if (st.isEmpty()) st.push(i);
                else best = Math.max(best, i - st.peek());
            }
        }
        return best;
    }

"(()" → 2, ")()())" → 4. O(n) time, O(n) space.

  1. Remove the outermost parentheses of every primitive group.
Solution

Track the depth; keep a bracket only if it is not at depth 0 (opening) or does not return to depth 0 (closing).

    static String removeOuter(String s) {
        StringBuilder sb = new StringBuilder();
        int depth = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') { if (depth > 0) sb.append(c); depth++; }
            else { depth--; if (depth > 0) sb.append(c); }
        }
        return sb.toString();
    }

"(()())(())" → ()()().

  1. Check brackets in a real Java file, ignoring strings: extend the mini project to read a file line by line, keep one stack across lines, and also skip // comments.

Quick quiz

String a = "{[]}(";
String b = "{[()]}";
System.out.println(isValid(a) + " " + isValid(b));
  • true true
  • false true
  • true false
  • false false
Answer

false true. In a, everything matches except the final (, which is still on the stack at the end. b closes every bracket in order. (Real output: false true.)

Interview questions

  1. Why a stack? The bracket that must close next is always the most recently opened one: last in, first out.
  2. Why does counting fail? It forgets the type and the order: "([)]" and "(]" have balanced counts.
  3. When is counting enough? With only one bracket type (e.g. minimum adds to make (/) valid).
  4. Time and space? O(n) time; O(n) space in the worst case (all openers, e.g. "((((").
  5. Which Java class for a stack? ArrayDeque via the Deque interface; Stack is legacy and synchronized.
  6. What does pop() do on an empty ArrayDeque? Throws NoSuchElementException; poll() returns null instead.
  7. Quick rejection? Odd length → false; first character a closer → false.
  8. How would you report where the error is? Push indices instead of characters; the failing index or the leftover top index is the position.

Glossary

Term Meaning
Stack A collection where items are added and removed only at one end, the top
Push Add an item on top of the stack
Pop Remove the top item and return it
Peek Read the top item without removing it
LIFO Last in, first out: the last item pushed is the first popped
Deque Double-ended queue (said "deck"): add and remove at both ends
ArrayDeque Java's array-based deque; the recommended stack (push, pop, peek)
Character The object (wrapper) version of char, needed inside collections
Autoboxing Java converting char ↔ Character (and other primitives) automatically
NoSuchElementException Thrown by pop() on an empty ArrayDeque
Unexpected type Compile error when a primitive like char is used as a generic type
Valid (balanced) brackets Same type, correct order, nothing left open
O(n²) Work that grows with the square of the input length
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Rubbing out pairs is correct but O(n²): one pair per pass on nested input, so it times out on 2 lakh characters.
  • Counting is O(n) but wrong with several bracket types: it forgets type and order.
  • A stack matches the rule "last opened, first closed": push openers; on a closer, check empty, pop, compare; at the end the stack must be empty.
  • O(n) time, O(n) space; in Java use Deque<Character> stack = new ArrayDeque<>().

Next episode: Monotonic stack: next greater element, daily temperatures.