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

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)

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.

Signing Off