LESSON 337 OF 442 · STACK

Create Maximum Number in Go: Monotonic Stack and Greedy Merge

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

Constraints:

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n

STEP 1 OF 27

Guided

Ctrl + Enter to check

GO · STACK

Create Maximum Number in Go, explained

Problem overview

maxNumber(nums1 []int, nums2 []int, k int) receives two slices of digits, each representing a number, and a length k that is at most len(nums1) + len(nums2). It must build the largest possible number of exactly k digits by picking digits from the two slices, with one rule: digits taken from the same slice keep their original relative order. The result is a slice of the k digits.

For nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3] and k = 5 the answer is [9, 8, 6, 5, 3]: the 9 and 8 from nums2, then the 6 and 5 from nums1, and the final 3 from nums2. For [6, 7], [6, 0, 4] and k = 5, all the digits are used, and the best interleaving is [6, 7, 6, 0, 4].

Approach: split the choice into three simpler problems

Choosing digits from two slices at once is hard. It becomes easy when it is split into pieces.

Decide how many digits come from each slice. If i digits come from nums1, the other k - i come from nums2. Try every i from 0 to k and keep only the splits that are possible: i can't exceed len(nums1), and k - i can't exceed len(nums2).
For a given split, take the best digits from each slice separately. The largest number of exactly size digits that keeps the order of a single slice is built with a stack. This is the same idea as removing digits to get the smallest number, turned upside down.
Merge the two pieces into the largest number that keeps the order inside each piece.

Finally, compare the candidate numbers of all the splits and keep the largest. All candidates have k digits, so they compare like words in a dictionary: the first digit that differs decides.

The stack for one slice

To keep size digits from nums and make the number as large as possible, read the digits left to right. When a digit is bigger than the one on top of the stack, popping the smaller one moves the bigger digit toward the front, which makes the number larger. Popping is only allowed while enough digits remain to still reach size: the digits on the stack, plus the digits not yet read including the current one, must be more than size. A digit is pushed only while the stack holds fewer than size digits.

For [9, 1, 2, 5, 8, 3] and size = 3 the stack ends as [9, 8, 3]. The 1, 2 and 5 are popped when 8 arrives, and 3 is added at the end.

The merge

Merging is a greedy choice: take the first digit of whichever piece is larger. When the two first digits are equal, that is not enough. With [6, 7] and [6, 0, 4], both start with 6, but the 6 must come from the first piece, so that its 7 comes next. The right way is to compare everything that is left of each piece, digit by digit, and take from the one that is larger.

Step by step

Start with an empty best slice. Any candidate beats it.
Loop i from 0 to k inclusive. i is how many digits come from nums1.
Skip impossible splits with i <= len(nums1) && k-i <= len(nums2).
Get the best i digits of nums1 and the best k-i digits of nums2 from the helper maxSubsequence, into first and second.
Merge them into candidate with the helper merge.
Keep the larger one: if isGreater(candidate, 0, best, 0), replace best. After the loop, return best.
Write maxSubsequence(nums, size). It creates an empty stack and walks the indices of nums. The index matters because the number of digits still to come is len(nums) - i.
Pop while it helps and is affordable. The inner loop runs while the stack isn't empty, its top is smaller than nums[i], and len(stack)+len(nums)-i > size. Each pass pops with stack = stack[:len(stack)-1].
Push if there is room: when len(stack) < size, append nums[i]. Otherwise the digit is left out. Return the stack at the end.
Write merge(a, b). It keeps indices i and j into the two pieces, both starting at 0, and loops while either has digits left.
Take from a if what is left of a is greater than what is left of b, otherwise from b. Append the digit and advance that index. When the two remainders are equal, either choice gives the same number.
Write isGreater(a, i, b, j). It skips digits while both remainders still have digits and the digits are equal.
Decide at the first difference. a wins if b has run out (j == len(b)), or if a still has a digit and it is bigger than b[j]. When b runs out first, what is left of a is longer or equal, so taking from a is correct.

The solution in Go

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    best := []int{}
    for i := 0; i <= k; i++ {
        if i <= len(nums1) && k-i <= len(nums2) {
            first := maxSubsequence(nums1, i)
            second := maxSubsequence(nums2, k-i)
            candidate := merge(first, second)
            if isGreater(candidate, 0, best, 0) {
                best = candidate
            }
        }
    }
    return best
}

func maxSubsequence(nums []int, size int) []int {
    stack := []int{}
    for i := 0; i < len(nums); i++ {
        for len(stack) > 0 && stack[len(stack)-1] < nums[i] && len(stack)+len(nums)-i > size {
            stack = stack[:len(stack)-1]
        }
        if len(stack) < size {
            stack = append(stack, nums[i])
        }
    }
    return stack
}

func merge(a []int, b []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(a) || j < len(b) {
        if isGreater(a, i, b, j) {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }
    return result
}

func isGreater(a []int, i int, b []int, j int) bool {
    for i < len(a) && j < len(b) && a[i] == b[j] {
        i++
        j++
    }
    return j == len(b) || (i < len(a) && a[i] > b[j])
}

The Go details worth a closer look:

A stack is a slice. Pushing is append and popping is re-slicing, stack[:len(stack)-1]. Re-slicing copies nothing: it just makes the slice one element shorter, and the top is always stack[len(stack)-1]. The result of append must be assigned back, because it may return a slice with a new backing array.
Go's while is for. A for with only a condition, such as for i < len(a) || j < len(b), behaves like a while loop in other languages.
Condition order matters. In len(stack) > 0 && stack[len(stack)-1] < nums[i] && ..., the length test runs first, so stack[len(stack)-1] is never evaluated on an empty stack. Go stops at the first false operand of &&. In the same way, a[i] in the last line of isGreater is only read after the test i < len(a) has passed.
Parameters are copies. isGreater changes its own i and j while skipping equal digits. The caller's i and j in merge are not affected.
Helpers can come after the function that uses them. Go doesn't need a declaration before use at package level, so maxNumber can call functions defined below it.
Empty slices. []int{} is an empty slice, and maxSubsequence(nums, 0) returns one. The functions handle it as an ordinary slice of length 0.

Complexity

Let m and n be the lengths of the two slices.

Time. There are at most k + 1 splits. For each one, maxSubsequence runs on both slices in O(m + n), because each digit is pushed and popped at most once. The merge takes k steps, and each step may compare long remainders. A comparison stops at the first differing digit, but in the worst case, with many equal digits, it walks the whole remainder. That gives O(k²) for one merge and a loose bound of O(k * (m + n + k²)) overall. The comparison of a candidate with best adds O(k) per split.

Space: O(k) at a time, for the two stacks, the merged candidate and best. Candidates that lose are discarded.

Edge cases and common mistakes

Taking everything. With k = len(nums1) + len(nums2), only one split is possible, and the answer is just the best merge of the full slices.
One slice does all the work. i = 0 or i = k are valid splits when the other slice isn't needed. For [1, 2], [3] and k = 1, the answer is [3].
Zeros. The digits can be 0, and the result keeps leading zeros if they are forced: [0] and [0] with k = 2 give [0, 0].
Comparing only the next digits in the merge. For [6, 7] and [6, 0, 4], when ties go to the second piece, that picks its 6 first and produces [6, 6, 7, 0, 4], which is smaller than [6, 7, 6, 0, 4].
Popping without the budget check. Without len(stack)+len(nums)-i > size, the stack can end with fewer than size digits.
Forgetting the push limit. Without len(stack) < size, the stack can end up with more than size digits.
Looping i only up to k - 1. The split with all k digits from nums1 is lost.

Testing

nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5 gives [9, 8, 6, 5, 3].
nums1 = [6, 7], nums2 = [6, 0, 4], k = 5 gives [6, 7, 6, 0, 4].
nums1 = [3, 9], nums2 = [8, 9], k = 3 gives [9, 8, 9].
nums1 = [5, 1], nums2 = [2, 7], k = 4 gives [5, 2, 7, 1].

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free