You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.
Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.
Return an array of the k digits representing the answer.
Example 1:
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5 Output: [9,8,6,5,3]
Example 2:
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5 Output: [6,7,6,0,4]
Example 3:
Input: nums1 = [3,9], nums2 = [8,9], k = 3 Output: [9,8,9]
Constraints:
m == nums1.lengthn == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + nnums1 and nums2 do not have leading zeros.The key idea behind Create Maximum Number is to construct the lexicographically largest number of length k by selecting digits from two arrays while maintaining their original order. A common strategy combines greedy selection with a monotonic stack.
First, iterate over all possible splits of k between the two arrays. For each split, extract the maximum subsequence of the required length from each array using a monotonic decreasing stack. This ensures that smaller digits are removed when a larger digit appears, producing the best subsequence while preserving order.
Next, merge the two subsequences greedily. At every step, compare the remaining parts of both sequences and pick the one that forms the larger lexicographic result. Track the best result across all splits.
This approach efficiently explores valid combinations while maintaining optimal digit ordering. The overall time complexity is roughly O((m+n) * k^2) due to repeated merging and comparisons, with O(m+n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Build maximum subsequence using Monotonic Stack | O(n) | O(k) |
| Merge two subsequences greedily | O(k^2) | O(k) |
| Overall algorithm across all splits | O((m+n) * k^2) | O(m+n) |
Ashish Pratap Singh
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Create Maximum Number is considered a challenging greedy and stack problem and has appeared in advanced technical interview practice sets. It tests understanding of monotonic stacks, greedy merging, and lexicographic comparison.
A monotonic stack is the most effective data structure for this problem. It helps maintain a decreasing sequence while selecting digits, ensuring that smaller digits are removed when a larger digit can improve the final number.
The optimal approach uses a greedy strategy with a monotonic stack. First, compute the maximum subsequence of required length from each array, then merge them by always selecting the lexicographically larger remaining sequence. Trying all valid splits of k ensures the best possible result.
Since the final number must have length k and digits can come from both arrays, we must consider all valid distributions of digits between them. Each split may produce a different maximum subsequence combination, so checking all possibilities guarantees the optimal result.