Create Maximum Number

Create Maximum Number

What is this problem about?

The Create Maximum Number interview question is a complex array manipulation task. You are given two integer arrays nums1 and nums2 of lengths m and n, and an integer k. You need to create the lexicographically largest array of length k using elements from both arrays while preserving the relative order of elements from each original array. You can pick i elements from nums1 and j elements from nums2 such that i + j = k.

Why is this asked in interviews?

Companies like Google and Bloomberg ask the Create Maximum Number coding problem to test a candidate's ability to decompose a complex problem into smaller, manageable subproblems. It requires mastering Monotonic Stacks, Greedy strategies, and Array merging. It evaluates your ability to optimize each part of the process to fit within time constraints, making it a high-level algorithmic challenge.

Algorithmic pattern used

This problem is solved by breaking it into three sub-tasks:

1. Select Maximum Subsequence: For each possible $i$ ($0 \le i \le k$), find the largest subsequence of length $i$ from nums1 and length $k-i$ from nums2 using a Monotonic Stack.
2. Merge Sequences: Merge the two subsequences to create the largest possible combined array. This requires a greedy comparison at each step.
3. Global Maximum: Keep track of the maximum merged array found across all possible splits of $k$.

Example explanation

nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5

1. If we take 2 from nums1 and 3 from nums2:
   • Max sub of nums1 (len 2): [6, 5]
   • Max sub of nums2 (len 3): [9, 8, 3]
2. Merge [6, 5] and [9, 8, 3]:
   • Pick 9 (from nums2), then 8 (from nums2), then 6 (from nums1), then 5 (from nums1), then 3 (from nums2).
   • Result: [9, 8, 6, 5, 3].
3. Repeat for other splits (e.g., 1 from nums1, 4 from nums2) and pick the best.

Common mistakes candidates make

• Naive Merging: Not realizing that when two elements are equal during merge, you must look ahead to subsequent elements to decide which array to pick from.
• Complexity: Trying to use 3D dynamic programming, which results in O(mnk), often too slow compared to the stack-based O(k*(m+n)) approach.
• Handling Constraints: Forgetting that $i$ must be at least $\max(0, k-n)$ and at most $\min(k, m)$.

Interview preparation tip

Master the "Largest Subsequence of length K" problem using a monotonic stack. It’s a building block for many "Hard" array problems and is essential for this specific question.