12.07Beginner / Intermediate5 topics18 min4 interactive animations

Classic stack patterns

Classic stack patterns: removing adjacent duplicates, asteroid collisions, simplifying a Unix path, decoding nested strings like 3[a2[c]] and the celebrity problem.

Learning goals

Recognise problems where the latest element interacts with the next
Use a stack of runs or frames
Decode nested structures with two stacks

Prerequisites

Expression problemsMonotonic stacks

12.07.1

Remove adjacent duplicates

To repeatedly delete adjacent equal characters (or runs of k equal characters), keep a stack of the surviving characters: a character equal to the top cancels it; otherwise it is pushed. For runs of k, store (character, run length) pairs and pop the pair when its count reaches k. Removing a run can make two earlier groups adjacent, which the stack handles naturally. O(n).

Try “abbaca” with k = 2 and a string that disappears completely.

Java

1static String removeDuplicates(String s) {                  // k = 2
2    StringBuilder stack = new StringBuilder();
3    for (char c : s.toCharArray()) {
4        int n = stack.length();
5        if (n > 0 && stack.charAt(n - 1) == c) stack.deleteCharAt(n - 1);
6        else stack.append(c);
7    }
8    return stack.toString();
9}

Remove adjacent duplicates with a stack

Interactive · edit the input

char[] s · length 6

012345

ReadingKept so farRemoved

stack of runs (char × count)

empty

Setup

Each stack entry is a run of equal characters with its length. When a run reaches 2, it disappears and the characters before it become adjacent.

Step 1 / 8

Java

1static String removeDuplicates(String s, int k) {
2    Deque<int[]> stack = new ArrayDeque<>();                       // {character, run length}
3    for (char c : s.toCharArray()) {
4        if (!stack.isEmpty() && stack.peek()[0] == c) {
5            if (++stack.peek()[1] == k) stack.pop();               // the run reached k: erase it
6        } else stack.push(new int[]{c, 1});
7    }
8    StringBuilder sb = new StringBuilder();
9    for (Iterator<int[]> it = stack.descendingIterator(); it.hasNext(); ) { int[] e = it.next(); sb.append(String.valueOf((char) e[0]).repeat(e[1])); }
10    return sb.toString();
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2		Each stack entry is a run of equal characters with its length. When a run reaches 2, it disappears and the characters before it become adjacent.
2	L4	i=0 c='a' runs=1	'a' differs from the top (or the stack is empty): start a new run.
3	L4	i=1 c='b' runs=2	'b' differs from the top (or the stack is empty): start a new run.
4	L4	i=2 c='b' runs=1	'b' extends the top run to 2: erase the whole run.
5	L4	i=3 c='a' runs=0	'a' extends the top run to 2: erase the whole run.
6	L4	i=4 c='c' runs=1	'c' differs from the top (or the stack is empty): start a new run.
7	L4	i=5 c='a' runs=2	'a' differs from the top (or the stack is empty): start a new run.
8	L10	return="ca"	Result "ca". One pass, O(n) time and space.

12.07.2

Asteroid collision

Asteroids move along a line: positive values go right, negative go left, the magnitude is the size. Two asteroids collide only when a right-mover is followed by a left-mover. Keep a stack of survivors: an incoming left-mover pops smaller right-movers, destroys itself against a bigger one and takes an equal one with it; anything else is pushed. O(n), because each asteroid is pushed and popped at most once.

Try the chain-reaction preset [10, 2, -5].

Java

1static int[] asteroidCollision(int[] a) {
2    Deque<Integer> stack = new ArrayDeque<>();
3    for (int x : a) {
4        boolean alive = true;
5        while (alive && x < 0 && !stack.isEmpty() && stack.peek() > 0) {
6            if (stack.peek() < -x) stack.pop();
7            else { if (stack.peek() == -x) stack.pop(); alive = false; }
8        }
9        if (alive) stack.push(x);
10    }
11    int[] out = new int[stack.size()]; int i = out.length;
12    for (int v : stack) out[--i] = v;
13    return out;
14}

Asteroid collision (stack of survivors)

Interactive · edit the input

int[] arr · length 3

-5

012

Arriving asteroidProcessedExploded

survivors (stack, top is last)

empty

Setup

Positive asteroids move right, negative move left. Only a right-mover on the stack followed by a left-mover can collide.

Step 1 / 5

Java

1static int[] asteroidCollision(int[] a) {                      // sign = direction, abs = size
2    Deque<Integer> stack = new ArrayDeque<>();
3    for (int x : a) {
4        boolean alive = true;
5        while (alive && x < 0 && !stack.isEmpty() && stack.peek() > 0) {   // right-mover meets left-mover
6            if (stack.peek() < -x) stack.pop();                  // the stack asteroid is smaller: it explodes
7            else { if (stack.peek() == -x) stack.pop(); alive = false; }   // equal: both explode; bigger: x explodes
8        }
9        if (alive) stack.push(x);
10    }
11    int[] out = new int[stack.size()]; int i = out.length;
12    for (int v : stack) out[--i] = v;                              // the stack holds the survivors, top first
13    return out;
14}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2		Positive asteroids move right, negative move left. Only a right-mover on the stack followed by a left-mover can collide.
2	L9	x=5	5 moves right: it cannot hit anything already behind it. Push.
3	L9	x=10	10 moves right: it cannot hit anything already behind it. Push.
4	L7	x=-5 top=10	10 meets -5: the right-mover is bigger, so -5 explodes.
5	L13	return=[5, 10]	Survivors [5, 10]. Each asteroid is pushed and popped at most once: O(n).

12.07.3

Simplify path

To canonicalise an absolute Unix path, split it on / and process the parts with a stack of directory names: skip empty parts and ., pop on .. (never above the root) and push anything else. Join the stack with /, or return / if it is empty. Note that ... is an ordinary name. O(n).

Try /a/./b/../../c/ and /../.

Java

1static String simplifyPath(String path) {
2    Deque<String> stack = new ArrayDeque<>();
3    for (String part : path.split("/")) {
4        if (part.isEmpty() || part.equals(".")) continue;
5        if (part.equals("..")) { if (!stack.isEmpty()) stack.pop(); }
6        else stack.push(part);
7    }
8    StringBuilder sb = new StringBuilder();
9    for (Iterator<String> it = stack.descendingIterator(); it.hasNext(); ) sb.append('/').append(it.next());
10    return sb.length() == 0 ? "/" : sb.toString();
11}

Simplify a Unix path with a stack

Interactive · edit the input

split("/") parts

(empty)0

..4

..5

(empty)7

stack of directories (top is last)

empty

Setup

Split on '/'; empty parts and '.' change nothing, '..' goes up one level, anything else enters a directory.

Step 1 / 10

Java

1static String simplifyPath(String path) {
2    Deque<String> stack = new ArrayDeque<>();
3    for (String part : path.split("/")) {
4        if (part.isEmpty() || part.equals(".")) continue;          // empty (from //) or the current directory
5        if (part.equals("..")) { if (!stack.isEmpty()) stack.pop(); }   // up one level, never above the root
6        else stack.push(part);                                       // a real directory name
7    }
8    StringBuilder sb = new StringBuilder();
9    for (Iterator<String> it = stack.descendingIterator(); it.hasNext(); ) sb.append('/').append(it.next());
10    return sb.length() == 0 ? "/" : sb.toString();
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3		Split on '/'; empty parts and '.' change nothing, '..' goes up one level, anything else enters a directory.
2	L4	part=""	An empty part (from a repeated or trailing slash): skip.
3	L6	part="a"	'a' is a directory: push it.
4	L4	part="."	'.' means the current directory: skip.
5	L6	part="b"	'b' is a directory: push it.
6	L5	part=".."	'..': go up, so pop 'b'.
7	L5	part=".."	'..': go up, so pop 'a'.
8	L6	part="c"	'c' is a directory: push it.
9	L4	part=""	An empty part (from a repeated or trailing slash): skip.
10	L10	return="/c"	Canonical path "/c": join the stack from bottom to top with '/'. O(n) time.

12.07.4

Decode string

Decode k[encoded] where encoded may itself contain such groups, as in 3[a2[c]] = accaccacc. Keep the current string and a pending number. On [ push both on two stacks and start fresh; on ] pop the saved string and count and append the current string repeated count times; digits extend the number, letters extend the string. The stacks hold one frame per open bracket, like a recursive parser's call stack. Time is O(output length).

Step through 3[a2[c]] and watch the two stacks.

Java

1static String decode(String s) {
2    Deque<Integer> counts = new ArrayDeque<>(); Deque<StringBuilder> strings = new ArrayDeque<>();
3    StringBuilder cur = new StringBuilder(); int num = 0;
4    for (char c : s.toCharArray()) {
5        if (Character.isDigit(c)) num = num * 10 + (c - '0');
6        else if (c == '[') { counts.push(num); strings.push(cur); cur = new StringBuilder(); num = 0; }
7        else if (c == ']') { StringBuilder prev = strings.pop(); prev.append(cur.toString().repeat(counts.pop())); cur = prev; }
8        else cur.append(c);
9    }
10    return cur.toString();
11}

Decode string: 3[a2[c]] with two stacks

Interactive · edit the input

char[] s · length 8

[

]

01234567

ReadingConsumed

counts stack

empty

saved strings stack

empty

current string · pending number

Setup

Digits build the repeat count. A '[' saves the current context (count and text so far) on two stacks and starts fresh; a ']' repeats the inner text and appends it to the saved text.

Step 1 / 10

Java

1static String decode(String s) {
2    Deque<Integer> counts = new ArrayDeque<>(); Deque<StringBuilder> strings = new ArrayDeque<>();
3    StringBuilder cur = new StringBuilder(); int num = 0;
4    for (char c : s.toCharArray()) {
5        if (Character.isDigit(c)) num = num * 10 + (c - '0');
6        else if (c == '[') { counts.push(num); strings.push(cur); cur = new StringBuilder(); num = 0; }   // save the context
7        else if (c == ']') { StringBuilder prev = strings.pop(); prev.append(cur.toString().repeat(counts.pop())); cur = prev; }
8        else cur.append(c);
9    }
10    return cur.toString();
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3		Digits build the repeat count. A '[' saves the current context (count and text so far) on two stacks and starts fresh; a ']' repeats the inner text and appends it to the saved text.
2	L5	i=0 c='3' depth=0	Digit 3: pending count becomes 3.
3	L6	i=1 c='[' depth=1	'[': push count 3 and the text "" so far, then start an empty inner string.
4	L8	i=2 c='a' depth=1	'a': append to the current string.
5	L5	i=3 c='2' depth=1	Digit 2: pending count becomes 2.
6	L6	i=4 c='[' depth=2	'[': push count 2 and the text "a" so far, then start an empty inner string.
7	L8	i=5 c='c' depth=2	'c': append to the current string.
8	L7	i=6 c=']' depth=1	']': repeat "c" 2 times and append it to the saved "a".
9	L7	i=7 c=']' depth=0	']': repeat "acc" 3 times and append it to the saved "".
10	L10	return="accaccacc"	Decoded: "accaccacc". The stacks hold one frame per open bracket, like the call stack of a recursive parser.

12.07.5

Celebrity problem

In a group of n people a celebrity is known by everyone and knows no one. Given a knows(a, b) test, push everyone on a stack; repeatedly pop two people a and b: if a knows b, a cannot be the celebrity, otherwise b cannot be, so push the one who might be. After n - 1 comparisons one candidate remains; verify it with 2(n - 1) more calls. O(n) calls to knows in total, instead of O(n²).

The matrix of who-knows-whom would need a different visual, so this item uses code only.

Java

1static int findCelebrity(boolean[][] knows) {               // knows[a][b]: a knows b
2    int n = knows.length;
3    Deque<Integer> stack = new ArrayDeque<>();
4    for (int i = 0; i < n; i++) stack.push(i);
5    while (stack.size() > 1) {
6        int a = stack.pop(), b = stack.pop();
7        stack.push(knows[a][b] ? b : a);                    // the one who may still be a celebrity stays
8    }
9    int c = stack.pop();
10    for (int i = 0; i < n; i++) if (i != c && (knows[c][i] || !knows[i][c])) return -1;
11    return c;
12}

Practice ladder

Now try it yourself

Easy

Remove adjacent duplicates from “abbaca”
Simplify /home//user/../docs/

Medium

Decode 2[ab3[c]]d
Resolve the asteroids [8, -8] and [10, 2, -5]

Advanced

Remove k adjacent duplicates (k = 3) and explain why the run-length stack is needed

Key takeaways

When the newest element can cancel or merge with the previous one, think stack.
Stacks of runs, frames or survivors keep these problems linear.
Nested structures decode with a stack frame per open bracket.