LESSON 337 OF 442 · STACK

Create Maximum Number in Kotlin: Stack, Merge and Try Every Split

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

KOTLIN · STACK

Create Maximum Number in Kotlin, explained

Problem overview

maxNumber(nums1, nums2, k) receives two IntArray values whose elements are digits from 0 to 9, plus a length k with 1 <= k <= nums1.size + nums2.size. It must build the largest possible number of exactly k digits, using digits from both arrays, and return its digits as an IntArray. Digits taken from the same array must keep their original relative order, but digits from different arrays can be interleaved in any way.

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 digits 9, 8 and 3 come from nums2, and the 6 and 5 from nums1. For nums1 = [6, 7], nums2 = [6, 0, 4] and k = 5 all digits must be used, and the best order is [6, 7, 6, 0, 4].

Since all candidates have the same length, "larger number" means larger as a digit sequence compared from the left: the first position where two candidates differ decides.

Approach: split, shrink, merge, compare

The answer takes some number i of digits from nums1 and the remaining k - i from nums2. Nobody knows the right i in advance, so the solution tries every split from 0 to k, skipping those that ask for more digits than an array has. For each split, the problem breaks into three smaller ones:

Best i digits of nums1. Choose the largest number of exactly i digits that keeps their order. Do the same for k - i digits of nums2.
Merge the two results into the largest possible interleaving.
Compare this candidate against the best seen so far and keep the larger.

The best subsequence uses a stack, in the same spirit as removing digits to make a number as small as possible, turned the other way around. Read the digits left to right. If the digit on top of the stack is smaller than the new digit, throwing the old one away and letting the new one move left makes the number bigger, so pop it. The only limit is that you must still be able to end with exactly size digits: a pop is allowed only if the digits already on the stack, plus the current digit and all digits still to come, add up to more than size. A digit that arrives when the stack is already full is dropped.

For [9, 1, 2, 5, 8, 3] and size = 3: 9 is pushed; 1 is pushed; 2 pops 1; 5 pops 2; 8 pops 5; 3 doesn't beat the 8, and the stack has room, so it is pushed. The result is [9, 8, 3].

The merge repeatedly takes the first digit of whichever remaining sequence is greater. When the next digits are equal, looking at them alone isn't enough, so the comparison goes further and compares the whole remaining tails. For [6, 7] and [6, 0, 4] both start with 6, but the first tail continues with 7 and the second with 0, so the 6 should come from the first array. Taking it from the second would produce [6, 6, 7, 0, 4], which is smaller than [6, 7, 6, 0, 4].

For the first example, the splits give these candidates:

digits from nums1 (i)	from nums2	best of each	merged
0	5	[] and [9, 2, 5, 8, 3]	92583
1	4	[6] and [9, 5, 8, 3]	96583
2	3	[6, 5] and [9, 8, 3]	98653
3	2	[4, 6, 5] and [9, 8]	98465
4	1	[3, 4, 6, 5] and [9]	93465

The split i = 5 is skipped, because nums1 has only four digits. The largest candidate is 98653, the expected answer.

Step by step

Start with an empty best. var best = IntArray(0) loses to any candidate, so the first candidate replaces it.
Try every split. for (i in 0..k) uses an inclusive range: i digits come from nums1, k - i from nums2.
Skip impossible splits. Neither array can give more digits than it has.
Shrink each array. maxSubsequence returns the best i digits of nums1 as first and the best k - i digits of nums2 as second.
Merge them into candidate, a k-digit array.
Keep the larger. isGreater(candidate, 0, best, 0) compares both from index 0, and a bigger candidate replaces best.
Return best after the loop.
Write maxSubsequence(nums, size). It's a private helper that returns the largest size-digit subsequence of nums.
Allocate the stack. IntArray(size) is enough, because the stack never holds more than size digits. count tracks how many are in use, so the top is stack[count - 1].
Visit each index. nums.indices provides the position, which is needed to know how many digits are left.
Pop while it helps. Pop when the stack isn't empty, its top is smaller than nums[i], and count + nums.size - i > size, meaning enough digits would still remain.
Popping is just count--. The old digit stays in the array and the next push overwrites it.
Push only if there is room: count < size.
Store the digit at stack[count] and increase count.
Return the stack.
Write merge(a, b). Another private helper, which interleaves two arrays into the largest number that uses all digits.
Allocate result with a.size + b.size slots.
Keep two cursors. i walks a and j walks b.
Loop until both are used up: i < a.size || j < b.size. Each turn takes exactly one digit.
Compare the tails. isGreater(a, i, b, j) says whether what is left of a beats what is left of b.
If so, take from a: store a[i] at result[i + j], since i + j digits are already placed, and advance i.
Otherwise take from b. When the tails are equal, either choice gives the same number.
Return result.
Write isGreater(a, aStart, b, bStart). It compares the tail of a from aStart with the tail of b from bStart.
Copy the starts into vars named i and j, because parameters are read-only in Kotlin.
Skip equal digits. The loop runs while both tails have digits and the digits at i and j are equal.
Advance both cursors on each equal pair.
Decide. a wins if b ran out first, or if a still has a digit that is larger than b[j].

The solution in Kotlin

class Solution {
    fun maxNumber(nums1: IntArray, nums2: IntArray, k: Int): IntArray {
        var best = IntArray(0)
        for (i in 0..k) {
            if (i <= nums1.size && k - i <= nums2.size) {
                val first = maxSubsequence(nums1, i)
                val second = maxSubsequence(nums2, k - i)
                val candidate = merge(first, second)
                if (isGreater(candidate, 0, best, 0)) {
                    best = candidate
                }
            }
        }
        return best
    }

    private fun maxSubsequence(nums: IntArray, size: Int): IntArray {
        val stack = IntArray(size)
        var count = 0
        for (i in nums.indices) {
            while (count > 0 && stack[count - 1] < nums[i] && count + nums.size - i > size) {
                count--
            }
            if (count < size) {
                stack[count] = nums[i]
                count++
            }
        }
        return stack
    }

    private fun merge(a: IntArray, b: IntArray): IntArray {
        val result = IntArray(a.size + b.size)
        var i = 0
        var j = 0
        while (i < a.size || j < b.size) {
            if (isGreater(a, i, b, j)) {
                result[i + j] = a[i]
                i++
            } else {
                result[i + j] = b[j]
                j++
            }
        }
        return result
    }

    private fun isGreater(a: IntArray, aStart: Int, b: IntArray, bStart: Int): Boolean {
        var i = aStart
        var j = bStart
        while (i < a.size && j < b.size && a[i] == b[j]) {
            i++
            j++
        }
        return j == b.size || (i < a.size && a[i] > b[j])
    }
}

Kotlin details worth a look:

0..k includes k. To exclude the end, use 0 until k. The solution needs the inclusive form because taking all k digits from nums1 is a valid split.
IntArray(size) starts filled with zeros. That matters in maxSubsequence. Without the count + nums.size - i > size guard, the stack can finish short: for [1, 9, 2] and size = 3 the code would pop the 1 and return [9, 2, 0], with a zero that came from the array's initial value and not from the input.
Short-circuit operators. In isGreater, j == b.size || (i < a.size && a[i] > b[j]) only reads a[i] after checking i < a.size and only reads b[j] after j == b.size was found false. Reordering the conditions could cause an index error.
Parameters are val. aStart can't be incremented, so the helper copies it into var i.
Returning an array hands over the same array that was built, with no copy. The function replaces best by reference when a candidate wins.
private helpers are called from maxNumber by name, because they sit in the same class.

Complexity

Time. There are at most k + 1 splits. For each one, maxSubsequence makes one pass over each array, so O(m + n) where m and n are the array sizes. Each merge produces k digits, and each of those turns can call isGreater, which may walk a long run of equal digits: up to O(k) per call, so a merge costs O(k²) in the worst case. Comparing the candidate with best costs O(k). The total is therefore bounded by O(k × (m + n + k²)).

Space: O(k). At any time the function holds the two stacks, the merged candidate and best, each of at most k digits.

Edge cases and common mistakes

k equals m + n. Only one split is possible, with every digit used. The merge alone decides the answer, as in [6, 7] and [6, 0, 4].
One side contributes nothing. i = 0 or i = k means one array gives no digits. The empty array from IntArray(0) merges fine.
Ties in the merge. Comparing only the next digit and then choosing b on a tie gives a smaller number for [6, 7] and [6, 0, 4]. Compare the whole tails.
Skipping the "enough digits left" guard. The stack could end with fewer than size digits, and zeros would fill the gap.
Turning digits into a number. With up to 1000 digits, the value doesn't fit in an Int or a Long. Compare digit by digit, as isGreater does.
Trying impossible splits. Without the size check, maxSubsequence would be asked for more digits than the array holds.

Testing

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

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

Start learning free