Create Maximum Number - Solution & Explanation

Problem Overview: You are given two arrays of digits and an integer k. Pick digits from both arrays (preserving their relative order) to build the largest possible number of length k. The challenge is choosing the best subsequence from each array and merging them so the final number is lexicographically maximum.

Approach 1: Greedy Combine with Monotonic Stack (O((m+n)*k) time, O(m+n) space)

The optimal strategy splits the problem into two steps: choose the best subsequence from each array, then merge them into the largest possible result. For every valid split i where i digits come from nums1 and k-i from nums2, compute the maximum subsequence using a monotonic decreasing stack. Iterate through each array and pop smaller digits while you still have removals available, ensuring the remaining sequence is lexicographically largest.

After extracting the best subsequences, merge them greedily. Compare the remaining portions of both sequences and always append the one that forms the larger lexicographical suffix. This comparison step ensures that equal prefixes still produce the globally maximum result. The approach relies heavily on concepts from Greedy strategies and the Monotonic Stack pattern.

This method works because each subsequence is locally optimal and the merge step guarantees global optimality. Iterating across all splits ensures you evaluate every valid combination of contributions from both arrays.

Approach 2: Dynamic Programming Approach (O(m * n * k) time, O(m * n * k) space)

A dynamic programming formulation treats the problem as constructing the best number while iterating through both arrays. Define a DP state representing the best sequence of length t formed using the first i elements of nums1 and first j elements of nums2. For each step, either pick the current digit from nums1, pick from nums2, or skip elements while maintaining order.

The transition compares candidate sequences lexicographically and keeps the larger one. While conceptually straightforward, storing and comparing sequences inside the DP table increases both time and memory usage. This approach mainly serves as a conceptual baseline showing the full search space before optimization.

The DP model highlights how the greedy stack solution compresses the state space dramatically by extracting optimal subsequences first and only merging promising candidates. Arrays and sequence comparisons dominate the operations, which is why the problem often appears in discussions around Array manipulation and advanced greedy design.

Recommended for interviews: The greedy monotonic stack + merge approach is what interviewers expect. It demonstrates mastery of subsequence extraction, lexicographic comparison, and greedy reasoning. A brute-force or DP explanation shows you understand the search space, but the optimized greedy solution proves you can reduce complexity and handle edge cases efficiently.