LESSON 337 OF 442 · STACK

Create Maximum Number in Scala: Monotonic Stack and 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 29

Guided

Ctrl + Enter to check

SCALA · STACK

Create Maximum Number in Scala, explained

Problem overview

The method maxNumber(nums1: Array[Int], nums2: Array[Int], k: Int): Array[Int] receives two arrays of digits, which stand for two numbers, and a length k that is at most nums1.length + nums2.length. It must build the largest possible number of exactly k digits by choosing digits from both arrays, with one rule: digits taken from the same array keep their original relative order. Digits from the two arrays can be interleaved freely. The result is an array of 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 come from nums2, the 6 and 5 from nums1, and the last 3 from nums2. For nums1 = [6,7], nums2 = [6,0,4] and k = 5 every digit must be used, and the answer is [6,7,6,0,4]. Both arrays have 1 to 500 digits.

All candidate numbers have k digits, so "largest" means: compare from the left, and the first digit that differs decides.

Approach: split, shrink, merge

The problem is hard to attack all at once, so it is cut into three smaller ones.

Choose the split. Any answer takes i digits from nums1 and k - i from nums2. The code tries every i from 0 to k, skipping those where either array doesn't have enough digits.
For a given split, pick the best digits from each array. The best i-digit number that keeps the order of nums1 is computed separately, and so is the best (k - i)-digit number for nums2. This is the job of maxSubsequence.
Merge the two results into the largest k-digit number, keeping the order inside each. This is the job of merge.

The best candidate over all splits wins.

The best digits of one array: a stack

maxSubsequence(nums, size) reads the digits from left to right and keeps a stack. When the new digit is bigger than the digit on top, the top digit is a bad choice: removing it moves the bigger digit one place to the left, which makes the number larger. So the stack pops while the top is smaller than the new digit, but only if enough digits remain to still fill size places. That condition is count + nums.length - i > size: the digits on the stack, plus the current one and all the unread ones, must still exceed size after dropping one. Then the new digit is pushed if the stack isn't full.

For [3,4,6,5] and size = 2 the stack goes [3], then [4] (the 3 is popped, since 3 comes before a bigger 4 and enough digits remain), then [6], then [6,5]. The result is [6,5].

Merging two digit lists

To merge, repeatedly take the next digit from whichever list is better. Comparing only the two next digits fails on ties. With a = [6,7] and b = [6,0,4], both start with 6. Taking the first 6 from b leaves the other 6 to come next and pushes the 7 to third place, while taking it from a lets the 7 come second. The rule is to compare everything that remains: take from a if what is left of a is greater than what is left of b. isGreater skips over equal digits and decides at the first difference. If b runs out first, the rest of a counts as greater or equal, so taking from a is right.

On the first example, the splits give these candidates:

i = 0: [] + [9,2,5,8,3] -> 92583
i = 1: [6] + [9,5,8,3]  -> 96583
i = 2: [6,5] + [9,8,3]  -> 98653
i = 3: [4,6,5] + [9,8]  -> 98465
i = 4: [3,4,6,5] + [9]  -> 93465

Splits with i = 5 are skipped, because nums1 has only 4 digits. The largest candidate is 98653, the expected answer.

Step by step

Start with an empty best. var best = Array.empty[Int]. Any candidate beats it, so the first one replaces it.
Loop over the splits. i <- 0 to k includes k. Here i digits come from nums1 and the other k - i from nums2.
Skip impossible splits. Only go on when i <= nums1.length and k - i <= nums2.length.
Get the best digits of each array with maxSubsequence, into first and second.
Merge them into candidate, which has k digits.
Keep the larger. If isGreater(candidate, 0, best, 0), replace best. Both start at index 0.
End with best, with no return: the last expression is the method's value.
Write maxSubsequence. It is a private helper taking the array and size. The stack is an array of size digits, stack, and count says how many are in use. The top is stack(count - 1).
Visit each index with nums.indices, because the index tells how many digits remain.
Pop while it helps. The while loop runs as long as the stack isn't empty, the top is smaller than nums(i), and count + nums.length - i > size. Popping is just count -= 1: the old digit stays in the array and is overwritten by the next push.
Push if there's room. If count < size, store nums(i) at stack(count) and increase count. A digit that finds the stack full is left out. End with stack.
Write merge. It makes result with room for a.length + b.length digits and two indices, i and j, both starting at 0.
Loop until both are used. i < a.length || j < b.length: each pass places one digit.
Choose the source. If isGreater(a, i, b, j), store a(i) at result(i + j) and advance i. Otherwise store b(j) there and advance j. The index i + j is the number of digits placed so far. End with result.
Write isGreater. It takes both arrays and start indices. Parameters can't be reassigned in Scala, so it copies the starts into the variables i and j.
Skip equal digits. A while loop advances both while neither is exhausted and a(i) == b(j).
Decide. The result is j == b.length || (i < a.length && a(i) > b(j)): a wins if b ran out, or if a still has a digit and it is bigger.

The solution in Scala

class Solution {
    def maxNumber(nums1: Array[Int], nums2: Array[Int], k: Int): Array[Int] = {
        var best = Array.empty[Int]
        for (i <- 0 to k) {
            if (i <= nums1.length && k - i <= nums2.length) {
                val first = maxSubsequence(nums1, i)
                val second = maxSubsequence(nums2, k - i)
                val candidate = merge(first, second)
                if (isGreater(candidate, 0, best, 0)) {
                    best = candidate
                }
            }
        }
        best
    }

    private def maxSubsequence(nums: Array[Int], size: Int): Array[Int] = {
        val stack = new Array[Int](size)
        var count = 0
        for (i <- nums.indices) {
            while (count > 0 && stack(count - 1) < nums(i) && count + nums.length - i > size) {
                count -= 1
            }
            if (count < size) {
                stack(count) = nums(i)
                count += 1
            }
        }
        stack
    }

    private def merge(a: Array[Int], b: Array[Int]): Array[Int] = {
        val result = new Array[Int](a.length + b.length)
        var i = 0
        var j = 0
        while (i < a.length || j < b.length) {
            if (isGreater(a, i, b, j)) {
                result(i + j) = a(i)
                i += 1
            } else {
                result(i + j) = b(j)
                j += 1
            }
        }
        result
    }

    private def isGreater(a: Array[Int], aStart: Int, b: Array[Int], bStart: Int): Boolean = {
        var i = aStart
        var j = bStart
        while (i < a.length && j < b.length && a(i) == b(j)) {
            i += 1
            j += 1
        }
        j == b.length || (i < a.length && a(i) > b(j))
    }
}

The Scala details worth a closer look:

Ranges. 0 to k includes k, while 0 until k would stop at k - 1. The split i = k takes every digit from nums1, so it is needed. nums.indices is the range 0 until nums.length.
Arrays. new Array[Int](size) creates an array filled with zeros, and elements are read and written with parentheses: stack(count - 1), stack(count) = nums(i). An Array has a fixed size, which is why the stack tracks its fill with count instead of resizing.
The stack array can be returned as is. It has exactly size slots, and the pop condition guarantees that all of them are filled by the end. When size is 0 the array is empty.
Last expression as the value. best, stack, result and the boolean in isGreater are the last lines of their methods, so they are the return values. No return keyword is needed.
private. The three helpers are visible only inside Solution. They can call each other in any order, because methods of a class can refer to later methods.
&& and || short-circuit. In i < a.length && a(i) > b(j) the index is only read when it is valid. In the while condition of isGreater, the two length checks come before a(i) == b(j) for the same reason.
Parameters are values. A method parameter, like aStart, can't be assigned to, hence the local var copies.

Complexity

Let m and n be the lengths of the arrays.

Time. There are at most k + 1 splits, and at most min(m, n) + 1 of them are valid. For each, maxSubsequence runs in O(m + n), since each digit is pushed and popped at most once. merge places k digits, and each placement may scan up to k digits in isGreater when the remainders are alike, so it is O(k²) in the worst case. Comparing the candidate with best costs O(k). All together, an upper bound is O(k × (m + n + k²)). The scan in isGreater stops at the first differing digit, so usual inputs are much faster than that bound.

Space: O(m + n). Each split creates two stack arrays, a merged array of k digits, and best holds one more k-digit array.

Edge cases and common mistakes

Taking everything from one array. For nums1 = [5,1,9], nums2 = [2] and k = 1, the splits are i = 0 (digit 2) and i = 1 (digit 9). The answer is [9].
Using all digits. With k = m + n only one split is valid, and the result is a merge of the two arrays as they are. The pop condition never allows a pop, because every digit is needed.
Ties in the merge. Comparing just a(i) and b(j) and always taking from b on a tie gives [6,6,7,0,4] for [6,7] and [6,0,4], which is smaller than the right answer [6,7,6,0,4]. Compare the whole remainders.
Popping too much. Without the count + nums.length - i > size test, the stack could throw away digits it needs, ending with fewer than size digits. For [1,9] and size = 2, the 1 must not be popped when the 9 arrives, and the test is what prevents it.
Zeros. The digits may be 0, and the answer may start with 0 if there is no choice, as [0,0] and [0] with k = 3 gives [0,0,0]. Compare digit by digit, not by converting to an Int or Long, which cannot hold up to 1000 digits.
Range off by one. 0 until k misses the split that takes all k digits from nums1.
Forgetting the split limits. Without the check on i and k - i, maxSubsequence gets a size larger than its array and returns a stack that isn't filled.

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,9], nums2 = [2], k = 1 gives [9].
nums1 = [0,0], nums2 = [0], k = 3 gives [0,0,0].

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

Start learning free