# Advent of Code 2025 - Day 3

**SPOILERS AHEAD!!!! DON’T READ WITHOUT TRYING**

Today’s Advent of Code puzzles were quite simple to come up with, the only issue/challenge that might come is about “implementation”

# Puzzle 1

Deduced Problem: Given a decimal digits string `num` find the maximum number that can be made using exactly 2 digits of `num`, maintaining their relative order

## Intuition and Logic

A simple brute force solution will involve iteration over `[0 … len(num) - 2]` with `i` as iterator and for each `i` we iterate over `[i + 1 … len(num) - 1]` with `j` as iterator to find maximum digit in `num[i+1:]`. Hence for each `num[i]` we have maximum in `num[i+1:]` as `num[j]` and therefore corresponding candidate for `num[i]` is made by `(i, j)`. We can do this for each `i` in `[0 … len(num) - 2]`. And from the candidates take the maximum result.

Time Complexity: \\(\Theta(n^2)\\)

## Improvement

For finding the maximum for each element in its suffix array instead of scanning the entire suffix array, we can maintain a `suffix_max` array, where `suffix_max[i]` is  
`max(num[i], max in [i+1 … len(nums - 1)]`  
Where we set the last element same as the last element in num as it has no suffix array.  
We can compute this `suffix_max` in a single pass(reverse one). And in another pass of `num`, we use `num[i]` and `suffix_max[i+1]` for making candidates and hence choosing the maximum.

## Implementation

```cpp
int max_joltage(string bank) {
        vector<char> suffix_max(bank.size());
        for (int i = bank.size() - 1; i >= 0; --i) {
                if (i == bank.size() - 1) {
                        suffix_max[i] = bank[i];
                }
                else {
                        suffix_max[i] = max(suffix_max[i + 1], bank[i]);
                }
        }
        int ans = INT_MIN;
        for (int i = 0; i < bank.size() - 1; ++i) {
                ans = max(ans, (bank[i] - '0') * 10 + (suffix_max[i + 1] - '0'));
        }
        return ans;
}
```

# Puzzle 2

Deduced Problem: Given a decimal digits string `num` find the maximum number that can be made using exactly 12 digits of `num`, maintaining their relative order

## Intuition and Logic

I came up with a simple solution

Start at start of string, and then find a maximum number such that there are still enough elements left to make a string of size `12`. Continue that until size 12 string is formed

## Implementation

1. start at `pos` = 0
    
2. loop over the count `remaining` that tells how many digits are left to select(initially 12 and goes till 0)
    
3. Find the position `last` such that we find max digit in `[pos … last]` and there are at least `remaining - 1` elements left to process
    
4. Find max in `[pos … last]` say at position `best_idx`.
    
5. Add that to result and set `pos = best_idx + 1`.
    
6. Repeat until `remaining = 0`.
    

I share the solution for any `k`(that is number of digits I have to choose)

```cpp
string max_subsequence_of_length(const string &num, int k = 12) {
    int n = (int)num.size();
    if (k >= n) return s;          // if input shorter or equal, return it
    string res;
    res.reserve(k);

    int pos = 0; // next index we can pick from
    for (int remaining = k; remaining > 0; --remaining) {
        // last index we can pick so that there remain (remaining-1) chars after it
        int last = n - remaining;
        // find maximum digit in s[pos..last]
        char best = '0';
        int best_idx = pos;
        for (int i = pos; i <= last; ++i) {
            if (num[i] > best) {
                best = num[i];
                best_idx = i;
                if (best == '9') break; // can't do better than '9'
            }
        }
        res.push_back(best);
        pos = best_idx + 1;
    }
    return res;
}
```

Time Complexity: \\(\Theta(n \cdot k)\\), in our case \\(\Theta(12n)\\).

# Conclusion

At last, it was one where you had to think more about robust implementation rather than approach and intuition. Follow me on X [@singhrounakkumr](https://x.com/singhrounakkumr).

*Signing Off*