Problem overview
The method maxNumber receives two arrays of digits, nums1 and nums2, and a length k with k <= nums1.count + nums2.count. Each array stands for a number, one digit per element. The task is to build the largest possible number of exactly k digits by choosing digits from the two arrays, keeping the relative order of the digits taken from the same array. 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, 8 and 3 come from nums2 in their original order, and the 6 and 5 from nums1. For [6, 7], [6, 0, 4] and k = 5 every digit is used, and the answer is [6, 7, 6, 0, 4].
Approach: try every split, solve each half, merge
A number with a fixed number of digits is larger when its first differing digit is larger, so it is compared like digits from the left. That suggests building the answer greedily, but there are two independent decisions: how many digits come from each array, and which digits and in what interleaving.
The solution splits the problem into three smaller ones:
- The split. Try every count
iof digits taken fromnums1, from 0 tok. The otherk - icome fromnums2. Skip splits that need more digits than an array holds. - The best subsequence of one array. For a fixed count, the largest number that keeps the order of an array is found with a stack. Walk through the digits, and while the digit on top of the stack is smaller than the current one, pop it, as long as enough digits remain to still fill the stack to its target size. A bigger digit that moves further left makes the number bigger.
- The merge. Given the best
i-digit number fromnums1and the best(k - i)-digit number fromnums2, interleave them into the largest number possible, each keeping its own order.
The best result over all splits is the answer. Each split is compared with the best so far, and the larger one is kept.
The merge deserves care. At each step it must take the next digit from the array whose remaining digits form the larger number, and comparing only the next two digits isn't enough when they are equal. For [6, 7] and [6, 0, 4], both arrays start with 6. Taking the 6 from [6, 0, 4] first gives [6, 6, 7, 0, 4], but taking it from [6, 7] first lets the 7 follow, giving the larger [6, 7, 6, 0, 4]. The rule that works is to compare everything that is left of the two arrays, and to take from the larger remainder. The helper isGreater does that comparison.
Step by step
- Keep the best so far in
var best: [Int] = []. Any real candidate beats the empty array, so the first valid split replaces it. - Loop over splits with
for i in 0...k. The closed range includesk, the case where every digit comes fromnums1.iis the number of digits fromnums1. - Skip impossible splits with the condition
i <= nums1.count && k - i <= nums2.count. An array can't give more digits than it has. - Find the best digits of each array with
maxSubsequence(nums1, i)andmaxSubsequence(nums2, k - i). - Merge them into one number of
kdigits:candidate. - Keep the larger. If
isGreater(candidate, 0, best, 0)says the candidate wins, it replacesbest. Both comparisons start at index 0. - Return
bestafter the loop. - Write
maxSubsequence, which takes an array and a number of digitssizeto keep, and returns an array. It is the stack idea from removing digits, turned around: a bigger digit pops the smaller ones in front of it. - Create the stack as an empty
[Int]namedstack, with the top at the end. - Loop over the indices with
for i in 0..<nums.count. The index is needed to know how many digits are still to come. - Pop while it helps. A
whileloop runs while the stack isn't empty, its top is smaller thannums[i], andstack.count + nums.count - i > size. That last test counts the digits held plus the digits still available, including the current one. Popping is allowed only when what remains can still fill allsizeplaces. - Pop the top with
removeLast(). - Push if there is room. If
stack.count < size, appendnums[i]. When the stack is full, the digit is dropped. - Return the stack.
- Write
merge, with two arrays and no argument labels, returning the largest number that uses all their digits in order. - Prepare the output: an empty
[Int]namedresult. - Keep one index per array,
iandj, both starting at 0. - Loop while digits remain:
while i < a.count || j < b.count. Each pass takes exactly one digit. - Ask which remainder is larger:
isGreater(a, i, b, j). - Take from
awhen it is: appenda[i]and advancei. - Otherwise take from
b: appendb[j]and advancej. If the remainders are equal, either choice gives the same number. - Return
result. - Write
isGreaterwith an arrayaand its start index, an arrayband its start index, returning aBool: whetherafrom its start is greater thanbfrom its start. - Copy the start indices into
varsiandj, because Swift parameters are constants. - Skip the equal prefix: a
whileloop runs while both have digits anda[i] == b[j]. - Advance both indices inside it.
- Decide.
awins whenbhas run out, or whenastill has a digit and it is bigger thanb[j].
The solution in Swift
class Solution {
func maxNumber(_ nums1: [Int], _ nums2: [Int], _ k: Int) -> [Int] {
var best: [Int] = []
for i in 0...k {
if i <= nums1.count && k - i <= nums2.count {
let first = maxSubsequence(nums1, i)
let second = maxSubsequence(nums2, k - i)
let candidate = merge(first, second)
if isGreater(candidate, 0, best, 0) {
best = candidate
}
}
}
return best
}
func maxSubsequence(_ nums: [Int], _ size: Int) -> [Int] {
var stack: [Int] = []
for i in 0..<nums.count {
while !stack.isEmpty && stack.last! < nums[i] && stack.count + nums.count - i > size {
stack.removeLast()
}
if stack.count < size {
stack.append(nums[i])
}
}
return stack
}
func merge(_ a: [Int], _ b: [Int]) -> [Int] {
var result: [Int] = []
var i = 0
var j = 0
while i < a.count || j < b.count {
if isGreater(a, i, b, j) {
result.append(a[i])
i += 1
} else {
result.append(b[j])
j += 1
}
}
return result
}
func isGreater(_ a: [Int], _ aStart: Int, _ b: [Int], _ bStart: Int) -> Bool {
var i = aStart
var j = bStart
while i < a.count && j < b.count && a[i] == b[j] {
i += 1
j += 1
}
return j == b.count || (i < a.count && a[i] > b[j])
}
}
Here is maxSubsequence on [9, 1, 2, 5, 8, 3] with size = 3. The stack grows like this: [9], then [9, 1]. The 2 pops the 1, because six digits are available for three places, giving [9, 2]. The 5 pops the 2 ([9, 5]) and the 8 pops the 5 ([9, 8]). The 3 is smaller than the 8, so it is pushed and the stack is full: [9, 8, 3].
The Swift details worth a closer look:
- The closed range
0...kincludesk, while0..<nums.countstops before the count. Both forms are used here, each for its purpose. stack.last!is an optional because an empty array has no last element. The exclamation mark unwraps it, and it is safe because!stack.isEmptycomes first and&&stops evaluating when the left side is false.- Methods calling methods. The four methods live in one class and call each other without
self.. - Parameters are constants. That is why
isGreatercopiesaStartandbStartinto the variablesiandjbefore moving them. - Arrays are values.
best = candidatecopies the array, in effect, and later changes to one never show up in the other. Swift copies the storage only when one of them is changed. - The final
returninisGreateris one boolean expression. Whenj == b.countis true, the right side is skipped, sob[j]is never read out of bounds.
Complexity
Time. There are at most k + 1 splits. For each valid split, maxSubsequence makes one pass over each array, which is O(m + n), since every digit is pushed and popped at most once. merge runs k iterations, and each isGreater call can scan up to k digits when the remainders share a long equal prefix, so one merge is O(k²) in the worst case and usually much less. A loose upper bound for the whole method is O(k × (m + n + k²)).
Space: O(m + n + k). The stacks hold at most size digits, the merged candidate and best hold k digits, and the arrays passed in are not copied until they change.
Edge cases and common mistakes
- Taking everything from one array. Splits with
i = 0ori = kare allowed when the arrays are long enough. The guard in theifexcludes them otherwise. kequal to the total length. The only valid split uses all digits, and the answer is the best interleaving of the full arrays:[6, 7, 6, 0, 4]in the example.- Merging by looking at one digit. Comparing only
a[i]andb[j], and sending ties tob, returns[6, 6, 7, 0, 4]for[6, 7]and[6, 0, 4]. The full remainder comparison is what returns[6, 7, 6, 0, 4]. - Popping too much. Without the
stack.count + nums.count - i > sizetest, the stack could end up with fewer thansizedigits. For[3, 4, 6, 5]andsize = 2the test keeps enough digits and the result is[6, 5]. - A size of 0.
maxSubsequence(nums, 0)returns an empty array, because nothing is ever pushed. The guard oniandk - ilets that case through when one array gives all the digits. - Zeros.
[0]and[0]withk = 2give[0, 0]. The answer is a list of digits, so there is no leading-zero problem. - Comparing candidates with the wrong tool. All candidates have exactly
kdigits, so a left-to-right digit comparison is correct. Converting them to integers would overflow, sincekcan be up to 1000.
Testing
nums1 = [3, 4, 6, 5],nums2 = [9, 1, 2, 5, 8, 3],k = 5returns[9, 8, 6, 5, 3].nums1 = [6, 7],nums2 = [6, 0, 4],k = 5returns[6, 7, 6, 0, 4].nums1 = [3, 9],nums2 = [8, 9],k = 3returns[9, 8, 9].nums1 = [5],nums2 = [7],k = 1returns[7].nums1 = [0],nums2 = [0],k = 2returns[0, 0].
