Build the Largest Number by Merging Two Digit Sequences

Implement maxNumberFromTwoArrays

Given two arrays of single digits nums1 and nums2, and an integer k, choose some digits from each (preserving each array's own relative order) so that the total number chosen is exactly k, then interleave the two chosen sequences (again preserving each side's relative order) to form the largest possible k-digit number. This combines two ideas already seen separately in this topic. First, extracting the largest length-m subsequence from a single array is the same monotonic-stack technique used for "smallest value after deleting digits" — just with the comparison flipped to keep bigger digits instead of smaller ones. Second, merging two already-chosen sequences into the largest possible interleaving is a greedy digit-by-digit comparison: at each step, take from whichever side's remaining sequence would form the larger continuation if compared digit by digit (falling back to whichever side is longer if one is a genuine prefix of the other). Trying every valid split of k between the two arrays and keeping the best merged result ties it all together.

Example 1:

Input: nums1 = [6,5,3], nums2 = [8,4,2], k = 3

Output: [8,6,5]

Example 2:

Input: nums1 = [2,7], nums2 = [6,7], k = 3

Output: [7,6,7]

Example 3:

Input: nums1 = [4,1,7], nums2 = [2,5], k = 4

Output: [5,4,1,7]

+ 3 hidden test cases run on Submit.

Constraints:

  • 1 ≤ nums1.length, nums2.length ≤ 4
  • 0 ≤ nums1[i], nums2[i] ≤ 9 (single decimal digits)
  • 1 ≤ k ≤ nums1.length + nums2.length

nums1 =

[6, 5, 3]

nums2 =

[8, 4, 2]

k =

3