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:
- every closing bracket is closed by the same type of opening bracket,
- brackets close in the correct order,
- 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.
- Opening bracket → push it.
- Closing bracket and the stack is empty → false (nothing to close).
- Otherwise pop the top: it must be the same type, else false.
- 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
- 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.
- 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.
- 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();
}
"(()())(())" → ()()().
- 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 truefalse truetrue falsefalse 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
- Why a stack? The bracket that must close next is always the most recently opened one: last in, first out.
- Why does counting fail? It forgets the type and the order:
"([)]"and"(]"have balanced counts. - When is counting enough? With only one bracket type (e.g. minimum adds to make
(/)valid). - Time and space? O(n) time; O(n) space in the worst case (all openers, e.g.
"(((("). - Which Java class for a stack?
ArrayDequevia theDequeinterface;Stackis legacy and synchronized. - What does
pop()do on an emptyArrayDeque? ThrowsNoSuchElementException;poll()returnsnullinstead. - Quick rejection? Odd length →
false; first character a closer →false. - 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.