Greedy Algorithms8 sections · 316 units
Open in Course

Create Maximum - Full Solution

Putting it together

Here is the complete approach:

function maxNumber(nums1, nums2, k)
 best := []
 for i from max(0, k - len(nums2)) to min(k, len(nums1))
 j := k - i
 candidate := merge(maxFromOne(nums1, i), maxFromOne(nums2, j))
 if candidate > best then
 best := candidate
 return best

Time: O(k(n+m))O(k \cdot (n + m)) for trying all splits and merging. Space: O(k)O(k).

The range of ii ensures both arrays have enough digits for the split.