Create Maximum Number
Hard · Greedy · Array · Two Pointers · Stack · Greedy · Monotonic Stack
Problem
You are given two arrays nums1 (length m) and nums2 (length n), each holding the decimal digits of a number, and an integer k with k <= m + n.
Build the largest possible number of exactly k digits by picking digits from the two arrays. Digits taken from the same array must keep their original relative order, but the two arrays may be interleaved freely.
Return the k digits of that number as an array.
Examples
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5 Output: [9,8,6,5,3]
Take 9 and 8 from nums2, then 6 and 5 from nums1, then 3 from nums2: 98653. No 5-digit choice can start with more than 9, 8.
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5 Output: [6,7,6,0,4]
All five digits are used. Taking the 6 of nums1 first lets its 7 come next: 6, 7, 6, 0, 4. Taking the other 6 first gives 6, 6, 7, 0, 4, which is smaller.
Input: nums1 = [3,9], nums2 = [8,9], k = 3 Output: [9,8,9]
Take 9 from nums1, then 8 and 9 from nums2: 989.
Constraints
- m == len(nums1), n == len(nums2)
- 1 <= m, n <= 500
- 0 <= nums1[i], nums2[i] <= 9
- 1 <= k <= m + n
Approaches
- Every split, pick each digit by scanning its window — time O(k · (m + n)² ), space O(m + n)
Follow-up
Why is the plain merge of two sorted lists wrong here? Try a = [6,7] and b = [6,0,4]: comparing only the front digits cannot decide between the two 6s.
Related problems
Start free on Cariara · Coding problems · System design studio
