Like lots of others, I’ve been enjoying Advent of Code again this year. One of the great things about it is that as well as the challenge and problem solving, there’s a large community which is also full of ideas. Having completed day 3 using a recursive function, a comment on Reddit mentioned that you could also solve this using a monotonic stack, which I’d never even heard about before, let alone used. So I decided to try it!

Problem

I’m solving part 2 of 2025’s day 3 puzzle, which can be summarised as ‘find the biggest 12-digit number from a bigger number, without rearranging the digits’.

The examples are

input: 987654321111111 -> 987654321111 (1's at end dropped)
input 811111111111119 -> 811111111119 (1's in middle dropped)
input 234234234234278 -> 434234234278 (2's/3's at start dropped)

This is also known as a ‘next greater element’ or ‘remove k elements’ puzzle if you want to search for more.

Solution

The answer to the puzzle is to go through all the digits and limit the search window to the required output length minus the number of digits you’ve already found. This ensures there are enough digits remaining to work through, otherwise the digits would end up out of order.

 result = []

 9876 54321111111
|    |   11 digits remaining to search

For the first number, we need to make sure that there are 11 digits still remaining so we can end up with a 12-digit number, so only the first 4 digits - 9, 8, 7, 6 - are in the window to be considered for the biggest number. We then check through these 4 digits and pick the biggest, 9, and add that to the result. We also need to save the position of the digit picked, in this case 0 (the first entry in the digit array).

 result = [9]

 9 8765 4321111111
  |    |   10 digits remaining to search

For the second pass, we’ve already picked 9 so we skip past that position, and we know we need to have 10 more digits for the result to have 12 digits, so the last 10 digits are also not considered. This leaves a window of 8, 7, 6, 5 to check - again, pick the biggest - 8 - and add to the result.

Since the input digits are in order, this progresses through until the result is the correct length. To see that the numbers are kept in order, use the second example 811111111111119 - 9 is only in scope to be checked for the last window:

 // already had 11 passes
 result = [81111111111]

  81111111111 1119
             |    | 15 (total input) - 11 (current result length) = 4 digits remaining to search

We pick the biggest number in the window - 9 - which shows why the middle 1’s are dropped.

Recursive

Since we need to do the same action repeatedly on different parts of the input, this feels like a good usecase for recursion! We can move along the input slice and repeatedly call the same function until we reach the end:

// recurse
fn find_x(chars: &[u8], mut collection: Vec<u8>, start: i32, to_find: usize) -> Vec<u8> {
    // base case: return if we've reached the end
    if to_find == 0 {
        return collection;
    }

    // create a window, to exclude the last found index and making sure there are
    // enough digits left over for the remainder (since digits have to stay in order)
    // we're finding 12 so make sure there are enough digits left over
    let end = chars.len() + 1 - to_find;

    let mut found = 0;
    let mut index = 0;
    let slice = &chars[(start + 1) as usize..end];

    slice.iter().enumerate().for_each(|(i, num)| {
        if *num > found {
            found = *num;
            index = i;
        }
    });

    collection.push(found);

    // index is for the slice, so add back chars index
    find_x(chars, collection, index as i32 + start + 1, to_find - 1)
}

Call the recursive function with a bit of setup - in this case, turn the line of input text into numbers, create an intermediate array (or stack) to store the results in as we move along the input, then convert the result array into a number to calculate the puzzle’s answer:

fn find_joltage(bank: &str, max_len: usize) -> u64 {
    // make stack
    let bytes = bank.as_bytes();

    // intermediate result to pass around the recursive function
    let collection = vec![];
    let stack = find_x(bytes, collection, -1, max_len);

    // roll it all up into a number for the puzzle
    stack
        .iter()
        .fold(String::new(), |acc, b| {
            acc + str::from_utf8(&[*b]).expect("Failed to parse")
        })
        .parse::<u64>()
        .expect("Failed to parse result")
}

Finally, call the function for each line in the puzzle input and add together the results:

fn calc_joltage(input: &str) -> u64 {
    let mut total = 0;
    for line in input.lines() {
        total += find_joltage(line, 12);
    }

    total
}

The biggest O of all

This works nicely, and is pretty quick! However, Big O strikes! The recursive algorithm repeatedly checks items in the array to make sure we’ve found the biggest in the window, so this code is O(nk) (where n = items in input and k = number of digits to find). This could push towards O(n2) if the number of digits to find is close to the length of the input. (Obviously here I’m ignoring the setup work, and for O(n2) the fact that we’ve optimised the search window). This is where the monotonic stack data structure improves things - using a stack can get an algorithm which runs in O(n) time, ie each item in the input array is only checked once.

Monotonic stack

A monotonic stack is a stack (ie a list) in which all the numbers are either always higher than the previous (increasing monotonic stack) or lower than the previous number (decreasing monotonic stack). We need an increasing monotonic stack, which means we need to loop through the input array, compare the current number to the last entry in the stack and replace the last entry if the current number is higher. Again, the trick here is to keep track of the window of numbers to check, to ensure that we don’t run out of numbers, as well as to make sure we don’t throw away the largest number we’ve already found.

// calling fn, same as before
fn calc_joltage(input: &str) -> u64 {
    let mut total = 0;
    for line in input.lines() {
        total += calc_joltage_stack(line);
    }

    total
}

fn calc_joltage_stack(input: &str, max_len: usize) -> u64 {
    let bytes = input.as_bytes();
    let mut stack = Vec::with_capacity(max_len);
    let mut window = bytes.len() - max_len;

    // single loop over the numbers in input
    for num in bytes {
        // if last is smaller, remove from stack and update window
        // window controls how many items we can remove
        // if it hits 0 then just add everything remaining in input
        while window > 0 && !stack.is_empty() && num > stack.last().expect("No elements in stack") {
            stack.pop();
            window -= 1;
        }
        stack.push(*num);
    }

    // as before, roll up answer into a number
    stack
        .iter()
        // if digits already in order then stack won't pop
        // so limit to max_len
        .take(max_len)
        .fold(String::new(), |acc, b| {
            acc + str::from_utf8(&[*b]).expect("Failed to parse")
        })
        .parse::<u64>()
        .expect("Failed to parse result")
}

To show what’s going on, here are the loops written out (the for num in bytes loop). Starting variables:

input: 234234234234278
window = 15 - 12 = 3

Loop 1

window = 3
stack = []
num = 2 (first in input)

window is greater than 0
stack is empty, so push
stack = [2]

Loop 2

window = 3 (unchanged from before)
stack = [2]
num = 3

window is greater than 0
stack is not empty
stack.last = 2
3 (num) is greater than 2 (stack.last)
remove last from stack and reduce window
stack = []
window = 2
stack is now empty so exit loop and push 3
stack = [3]

Loop 3

window = 2
stack = [3]
num = 4

window is greater than 0
stack is not empty
4 (num) is greater than 3 (stack.last)
remove from stack and reduce window
stack = []
window = 1
stack is empty so exit loop and push 4
stack = [4]

Loop 4

window = 1
stack = [4]
num = 2

window is greater than 0
stack is not empty
2 (num) is not greater than 4 (stack.last)
skip loop and push 2
stack = [4, 2]

Loop 5

window = 1
stack = [4, 2]
num = 3

window is greater than 0
stack is not empty
3 (num) is greater than 2 (stack.last)
remove last from stack and reduce window
stack = [4]
window = 0

window is now 0 so exit loop
push 3 (num) onto stack
stack = [4, 3]

Loop 6 (and onwards)

window = 0
stack = [4, 3]
num = 4

window is 0, so the pop loop is skipped from now on
push num to stack
stack = [4, 3, 4]

At this point, since window is 0 the numbers in input are pushed in order into the stack:

stack = [4, 3, 4, 2, 3, 4, 2, 3, 4, 2, 7, 8]

which is our answer, having only looped through the input once!