Create Maximum Number (LeetCode 321)

You get two arrays of digits, nums1 and nums2, and a number k. The goal is to build the biggest possible k-digit number using digits from both arrays. The tricky part is: digits that come from the same array have to stay in relative order. You can skip digits and interleave the two arrays however you want, but you can’t reorder an array.

For example, with nums1 = [3, 9], nums2 = [8, 9] and k = 3, the answer is [9, 8, 9]. The first 9 comes from nums1, and the 8 and the second 9 come from nums2, in their original order.

This monotonic stack problem was challenging for me but I felt like I learned a lot from it.

The idea

I split the problem into four small methods:

1. pickBest(arr, count) picks the best count digits out of one array, keeping their order.
2. greater(a, i, b, j) answers one question: is what’s left of a (starting at i) bigger than what’s left of b (starting at j)?
3. merge(a, b) zips two picked arrays into the biggest number it can, asking greater which side to take from at each step.
4. maxNumber tries every way to split k between the two arrays, and keeps the best result.

So for every split, I pick the best digits from each array, zip them together, and keep the biggest result.

Picking the best digits from one array

Say I have n digits and I want to keep count of them. That means I can throw away n - count digits. I call those my skips.

Digits further left are worth more: 92 beats 29, because the first digit matters most. So whenever a small digit is sitting right in front of a bigger one, I want to throw the small one away, because that slides the bigger digit one spot to the left.

My greedy rule is therefore:

• When a new digit shows up, look at the top of the stack. While the top is smaller than the new digit and I still have skips remaining, pop it and use up a skip.
• Then always push the new digit, regardless of what happened previously.

Here it is on [9, 1, 2, 5, 8, 3] with count = 3, so 3 skips:

That gives 983. Reading the stack from the bottom up, the digits never go up. That’s what makes it a monotonic (decreasing) stack: the big digits settle at the bottom, which is the front of the number.

Something I didn’t get at first is that it has to be a while, not an if. One new digit can pop a bunch of things off from our stack. In [3, 3, 6] with count = 1, the 6 has to pop both 3s. My comment in the code is about exactly that:

//Keep popping until top of stack holds the true biggest number
// 3 3 6<- top will eventually turn to just 6

Popping stops when the top is at least as big as the new digit, when the stack is empty, or when I’m out of skips.

Two more details:

• Ties don’t pop. The check is strictly <. Popping a 9 just to push another 9 wastes a skip. On [9, 9, 1] with count = 2, not popping gives 99, but popping on the tie spends the only skip and leaves me stuck with 91.
• Leftover skips. If the array was already decreasing, like [5, 4, 3] with count = 2, nothing ever gets popped, and the stack ends up longer than count. Since the stack is decreasing, the smallest and least important digits are on top, so I just keep the first count from the bottom: 54.

Comparing leftovers

The greater method lines up what’s left of each array (nums1 and nums2) and walks forward while the digits are equal. The first digit that’s different decides it. If one side runs out while everything so far was tied, the side that still has digits left wins. My comment for it is short:

//return true if a is supreme, false otherwise

The “longer side wins” rule is what makes the merge method work on ties. Take a = [6] and b = [6, 7]. If I take b’s 6 first, the 7 gets to come right after it, and I end up with 676. If I take a’s 6 first, I get 667. Taking from the side with more left gets its bigger digits to the front sooner.

Zipping two arrays together

merge looks a lot like the merge step in merge sort: one pointer into each array, take a digit, move that pointer forward. The difference is that these arrays aren’t sorted, so comparing just the two current digits isn’t enough. With [6, 7] and [6, 0, 4], the two current digits are both 6. If I picked b’s 6, I’d get [6, 6, 7, 0, 4]. Asking greater instead sees the 7 hiding behind a’s 6 and gives [6, 7, 6, 0, 4].

merge never checks whether a pointer has gone past the end. It doesn’t need to: once one side runs out, greater always says to take from the other one.

Trying every split

The one thing there’s no quick rule for is how many digits should come from each array. With k = 2 and nums2 = [8, 8]:

nums2 is the same every time, and the best split still changes. So I try all of them. i is how many digits come from nums1, and k - i come from nums2.

The part that confused me most was the loop going up to i <= k, not i < k. I thought the extra iteration meant grabbing an extra digit. It doesn’t. i is a count, not a position, and the counts 0 through k are k + 1 different splits. Each of those splits still makes exactly k digits. Both ends matter: i = 0 means everything comes from nums2, and i = k means everything comes from nums1.

Some splits are impossible, like asking a 2-digit array for 3 digits. A split only works if nums1 has at least i digits and nums2 has at least k - i, so I check exactly that and skip the rest:

if (i <= m && k - i <= n) {

Apparently you can also bake that check into the loop bounds. When I sought out an optimal or alternative approach to this, I found out you could do boundary conditions Math.max(0, k - n) up to Math.min(k, m). It’s the same rule, but my brain naturally tends to the if conditional I came up with.

The code

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] result = new int[k];
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i <= k; i++) {
            if (i <= m && k - i <= n) {
                int[] first = pickBest(nums1, i);
                int[] second = pickBest(nums2, k - i);
                int[] candidate = merge(first, second);
                if (greater(candidate, 0, result, 0)) {
                    result = candidate;
                }
            }
        }
        return result;
    }

    public int[] pickBest(int[] arr, int count) {
        int[] stack = new int[arr.length];
        int skipsAvailable = arr.length - count;
        int top = 0; //ptr to next available spot (also the current size) on my stack!
        stack[top++] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            //Keep popping until top of stack holds the true biggest number
            // 3 3 6<- top will eventually turn to just 6
            while (skipsAvailable > 0 && top != 0 && arr[i] > stack[top - 1]) {
                top--;
                skipsAvailable--;
            }
            stack[top++] = arr[i];
        }

        int[] bestDigits = new int[count];
        for (int j = 0; j < count; j++) {
            bestDigits[j] = stack[j];
        }
        return bestDigits;
    }

    public int[] merge(int[] a, int[] b) {
        //input is two arrays that came from pickBest
        //returns int[] of size a.length + b.length, using every digit from both arrays
        //maintains the relative order of both arrays
        int total = a.length + b.length;
        int[] merged = new int[total];
        int i = 0;
        int j = 0;
        int count = 0;
        while (count < total) {
            if (greater(a, i, b, j)) {
                merged[count] = a[i];
                i++;
            }
            else {
                merged[count] = b[j];
                j++;
            }
            count++;
        }
        return merged;
    }

    public boolean greater(int[] a, int i, int[] b, int j) {
        //return true if the 'a' array is supreme, false otherwise
        while (i < a.length && j < b.length) {
            int first = a[i];
            int other = b[j];
            if (first > other) {
                return true;
            }
            else if (first < other) {
                return false;
            }
            else {
                i++;
                j++;
            }
        }
        if (i < a.length && j == b.length) {
            return true;
        }
        if (i == a.length && j < b.length) {
            return false;
        }
        //tie breaking scheme, when both arrays a and b used up all their elements & are both identical
        //I'll just return true and say that 'a' won
        return true;
    }
}

result starts as new int[k], which Java fills with zeros, so the first real candidate always beats it. At the end of greater, both sides ran out at the same time, which means the leftovers were identical, so it doesn’t matter which one merge takes. I return true.

Swapping Stack for int[]

My first version of pickBest used a Stack<Integer> and passed in 57 ms. So…in summary, being inspired by the way I beat Alien Dictionary with just 2-3 ms runtime, I found that switching to a plain int[] brought it down to about 9 ms, with the exact same algorithm.

I was curious why this was the case, and I ended up learning online that Stack is an old Java class that locks on every operation, and Stack<Integer> wraps every digit in an Integer object. I also had to pop everything into an ArrayList and read it backwards to get the digits out in order. It was pretty great seeing how translating to int[] stack led to less code, faster runtime, though there is the real tradeoff of placing the burden on the developer to keep track of how all these damn indices are behaving + their use case. This would probably be unpleasant to revisit some months (or weeks lol) down the line.

p.s.: my Alien Dictionary, Faster, where swapping HashMaps for arrays made the same algorithm faster.

An array plus one counter does everything the Stack did:

top is both the size of the stack and the next free slot. Popping doesn’t actually erase anything: the old value is still sitting in the array, but anything at index top or above is treated as garbage, and the next push writes over it. The bottom of the stack is stack[0], so the digits are already in the right order, and getting the answer out is just copying the first count slots.

Runtime

Let m and n be the lengths of the two arrays. There are at most k + 1 splits. For each one, pickBest runs once over each array, which is $O(m + n)$, since every digit gets pushed once and popped at most once. merge fills k slots, and each call to greater can look ahead up to $O(k)$ digits, so merge is $O(k^2)$ in the worst case. Altogether that’s $O(k \cdot (m + n + k^2))$ in the worst case. In practice greater almost always finds a difference after a digit or two, so it’s much faster than that.

That sounds slow, but both arrays have at most 500 digits here, so it passes easily. For space, each split builds a stack of size $O(m + n)$ and a candidate of size $k$, so it’s $O(m + n + k)$.