Problem overview
The method maxNumber receives two arrays of digits, nums1 and nums2, and a length k with k <= m + n. Each array stands for a number written digit by digit. You pick exactly k digits from the two arrays together, keeping the order of the digits taken from the same array, and the digits you pick, read in the order you place them, form a number. The method returns the digits of the largest such number as 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 final 3 from nums2. Because the result always has exactly k digits, two answers compare like numbers of the same length: the first digit that differs decides.
Approach: split, shrink, merge, compare
The problem looks hard because the choices interact, but it breaks into three smaller problems.
- Fix the split. Any answer takes some number
iof digits fromnums1and the remainingk - ifromnums2. Try everyifrom 0 tok, skipping splits that ask for more digits than an array has. - Best digits per array. For a fixed split, the best result is made from the largest
i-digit subsequence ofnums1and the largest(k - i)-digit subsequence ofnums2. Choosing anything smaller from either array can't help. A monotonic stack finds each of these in one pass. - Best merge. Combine the two chosen subsequences into the largest possible sequence, each keeping its own order.
The best candidate over all splits is the answer.
The stack idea works like this. Read the digits left to right and keep a stack of the digits kept so far. If the new digit is bigger than the top, the top should go: removing a smaller digit in front of a bigger one moves the bigger digit left and increases the number. But a digit may only be popped if enough digits remain to still fill size places.
The trace for maxSubsequence([9, 1, 2, 5, 8, 3], 3), with the stack after each digit:
9 -> [9]
1 -> [9, 1]
2 -> pops 1 -> [9, 2]
5 -> pops 2 -> [9, 5]
8 -> pops 5 -> [9, 8]
3 -> [9, 8, 3]The merge is the delicate part. It repeatedly takes the first digit of the larger remainder. Comparing only the two next digits is wrong when they are equal: for [6, 7] and [6, 0, 4] both fronts are 6, but the 6 must come from the first array, so that its 7 follows. That gives [6, 7, 6, 0, 4]. Taking the 6 from the second array would give [6, 6, 7, 0, 4], which is smaller. So the comparison looks past equal digits, at the whole remainders.
Step by step
- Start with an empty
best. Any candidate beats an empty array. - Loop
ifrom 0 tokinclusive.iis the number of digits taken fromnums1. - Skip impossible splits with
i <= nums1.length && k - i <= nums2.length. - Get the best part of each array with the helper
maxSubsequence:firstfromnums1withidigits, andsecondfromnums2withk - idigits. - Merge them into
candidatewith the helpermerge. - Keep the larger.
isGreater(candidate, 0, best, 0)compares the two from index 0, and the winner becomesbest. - Return
bestafter the loop. - Write
maxSubsequence(nums, size). Create an emptystackand loop over the indexes ofnums. The index matters for counting how many digits remain. - Pop while it pays. The loop pops while the stack is non-empty, its top is smaller than
nums[i], andstack.length + nums.length - i > size. That last condition says that after dropping the top, the digits on the stack plus the unread digits, counting the current one, still reachsize. - Push if there is room:
nums[i]goes on the stack only whenstack.length < size. A digit that arrives at a full stack and couldn't replace anything is discarded. Returnstackat the end. - Write
merge(a, b). It keepsresultand two positionsiandjstarting at 0, and loops while either array has digits left. - Choose the side with
isGreater(a, i, b, j). If the remainder ofais greater, pusha[i]and advancei. Otherwise pushb[j]and advancej. When the remainders are equal, either choice gives the same number. - Write
isGreater(a, i, b, j). It skips forward while both arrays have digits and those digits are equal. After the skip it returnstrueifbran out (j === b.length), or ifastill has a digit and it is bigger thanb[j].
The solution in TypeScript
class Solution {
maxNumber(nums1: number[], nums2: number[], k: number): number[] {
let best: number[] = [];
for (let i = 0; i <= k; i++) {
if (i <= nums1.length && k - i <= nums2.length) {
let first = this.maxSubsequence(nums1, i);
let second = this.maxSubsequence(nums2, k - i);
let candidate = this.merge(first, second);
if (this.isGreater(candidate, 0, best, 0)) {
best = candidate;
}
}
}
return best;
}
maxSubsequence(nums: number[], size: number): number[] {
let stack: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (stack.length > 0 && stack[stack.length - 1] < nums[i] && stack.length + nums.length - i > size) {
stack.pop();
}
if (stack.length < size) {
stack.push(nums[i]);
}
}
return stack;
}
merge(a: number[], b: number[]): number[] {
let result: number[] = [];
let i = 0, j = 0;
while (i < a.length || j < b.length) {
if (this.isGreater(a, i, b, j)) {
result.push(a[i]);
i++;
} else {
result.push(b[j]);
j++;
}
}
return result;
}
isGreater(a: number[], i: number, b: number[], j: number): boolean {
while (i < a.length && j < b.length && a[i] === b[j]) {
i++;
j++;
}
return j === b.length || (i < a.length && a[i] > b[j]);
}
}
The TypeScript details worth a closer look:
- Arrays as stacks.
pushadds at the end andpopremoves from the end, both in constant time. The top of the stack isstack[stack.length - 1]. - Helper methods need
this.. Calls such asthis.merge(first, second)are required inside a class. Method order doesn't matter, somaxNumbercan call helpers defined below it. - Parameters are local copies of the reference. In
isGreater,i++andj++change only the function's own parameters, so the caller'siandjinmergestay put. The arrays are only read. - Short-circuiting. In
j === b.length || (i < a.length && a[i] > b[j]), the guards keepa[i]andb[j]from being read past the end. In JavaScript that read would giveundefined, and comparisons withundefinedare always false. - Digits are numbers, so comparison is numeric.
a[i] > b[j]compares numbers, which is what we want. Joining digits into a string and comparing it would also work only for equal lengths. - Aliasing.
best = candidatestores a reference. That is safe, becausecandidateis a fresh array on every iteration.
Complexity
Let m and n be the lengths of the two arrays.
Time: O(k × (m + n + k²)) in the worst case. There are at most k + 1 splits. For each, the two maxSubsequence calls cost O(m + n) together, since every digit is pushed and popped at most once. The merge takes k steps, and each isGreater call can walk up to k digits when the remainders agree for a long stretch, so a merge costs O(k²) in the worst case. Comparing candidate with best costs O(k). Typical inputs, where the remainders differ early, are much cheaper.
Space: O(k). Each stack holds at most size digits, the merged candidate has k, and best has k.
Edge cases and common mistakes
- One array contributes nothing. The split
i = 0takes all digits fromnums2, andi = ktakes all fromnums1.maxSubsequencewithsize0 returns an empty array, and merging with an empty array simply copies the other one. - Equal fronts in the merge.
merge([6, 7], [6, 0, 4])gives[6, 7, 6, 0, 4]. Merging by comparing only the next digit, and taking frombon ties, would give[6, 6, 7, 0, 4]formerge([6, 0, 4], [6, 7]), which is wrong. - Popping without the count guard. Without
stack.length + nums.length - i > size, the stack could shrink belowsizeand the result would be too short. FormaxSubsequence([1, 2, 3], 3)the answer must stay[1, 2, 3]. - Skipping the split check. Taking more digits than an array has would silently return a shorter list from
maxSubsequence, and the merged candidate would then have fewer thankdigits. - Looping to
k - 1. The split with allkdigits fromnums1would never be tried. - Zeros. Digits can be 0, so test numbers for "is empty" by length, never by truthiness:
[0]is a valid answer, and0is falsy.
Testing
nums1 = [3, 4, 6, 5],nums2 = [9, 1, 2, 5, 8, 3],k = 5gives[9, 8, 6, 5, 3].nums1 = [6, 7],nums2 = [6, 0, 4],k = 5gives[6, 7, 6, 0, 4].nums1 = [3, 9],nums2 = [8, 9],k = 3gives[9, 8, 9].nums1 = [0],nums2 = [0],k = 1gives[0].
