Create Maximum Number
Understanding the Problem
This problem asks us to build the largest possible number of exactly k digits, where each digit comes from either nums1 or nums2, and the relative order of digits within each source array is preserved. Stated another way: pick a subsequence from nums1 and a subsequence from nums2 whose lengths sum to k, then interleave them into the largest possible number.
What makes this hard is the interplay of three decisions: how many digits to take from each array, which digits to pick from each array, and how to merge the two picks into the largest result. Getting any one of these wrong produces a suboptimal answer. Each decision can be solved as its own subproblem: find the maximum subsequence of a given length from a single array, merge two subsequences into the largest result, and try every valid split of k between the two arrays.
Key Constraints:
1 <= m, n <= 500→ Both arrays are small. Trying every split ofkbetween the two arrays, with linear scans plus an O(k^2) merge per split, fits comfortably in the time limit.0 <= nums1[i], nums2[i] <= 9→ Only ten distinct values, so equal digits collide often and the merge step needs a tiebreak that looks past the front digit.1 <= k <= m + n→kcan exceed either array's length, so some splits are forced to take digits from both arrays.
Approach 1: Brute Force (Enumerate All Subsequences)
Intuition
Enumerate every possible way to pick k digits from the two arrays while preserving relative order, build each candidate number, and track the maximum.
This means generating all subsequences of every valid length from nums1, all subsequences of the complementary length from nums2, and every order-preserving interleaving of each pair. The counts explode: an array of length m has C(m, i) subsequences of length i, and a pair of picks can interleave in C(k, i) ways. With m and n up to 500, the candidate count is exponential.
Algorithm
- For each valid split i (number of digits from nums1), where max(0, k - n) <= i <= min(k, m):
- Generate all subsequences of length i from nums1.
- Generate all subsequences of length k - i from nums2.
- For each pair, generate every order-preserving interleaving and track the maximum.
- Return the overall maximum.
Visualization and Code
Loading animation...
- Time Complexity: O(C(m, i) C(n, k-i) C(k, i) * k) per split, summed over all splits: every subsequence pair, every interleaving of the pair, and O(k) to compare a candidate. Exponential in m and n.
- Space Complexity: O(m + n) for the recursion used to enumerate subsequences, plus O(k) for the current candidate.
Almost all of this work is wasted. For a fixed length, only the maximum subsequence of each array matters: any other subsequence of the same length can be swapped for the maximum one without making the merged result smaller. The next approach computes that single best subsequence per array in linear time and merges one pair of candidates per split.
Approach 2: Greedy Decomposition (Optimal)
Intuition
Instead of exploring all combinations, we decompose the problem into three subproblems:
- Max Subsequence: Given a single array and a target length t, find the lexicographically largest subsequence of length t. A monotonic stack solves this in one pass: walk left to right, and pop the top of the stack whenever the incoming digit is larger and enough digits remain in the array to still fill length t.
- Merge: Given two sequences, merge them into the largest possible result while preserving the internal order of each. Taking whichever front digit is larger fails when the fronts are equal. Merging [6, 7] and [6, 0, 4] must take the 6 from [6, 7] first: that order produces 67604, while consuming the other 6 first produces 66704. The tiebreak is to compare the remaining suffixes lexicographically and take from the larger one ([6, 7] beats [6, 0, 4] because 7 > 0 at the second position).
- Enumerate splits: Try every valid way to divide k between the two arrays (take i from nums1 and k - i from nums2), solve subproblems 1 and 2 for each split, and keep the best result.
For a fixed split, the answer must be built from the maximum subsequence of each array. If a candidate used a non-maximal subsequence from nums1, replacing it with the maximal subsequence of the same length never makes the merged result smaller, so checking only the two maximal subsequences cannot miss the optimum for that split.
In the merge, when the front digits differ, the larger one must go first: candidates are compared digit by digit from the left, so a larger digit in the current position beats any arrangement of the digits that follow. When the front digits are equal, the digit written is the same either way; the choice only affects which digits remain available. Taking from the side with the larger suffix keeps the stronger remaining digits closer to the front, which is what the [6, 7] and [6, 0, 4] example shows.
Algorithm
- For each valid split i, where max(0, k - n) <= i <= min(k, m):
- Compute sub1 = maxSubsequence(nums1, i): scan left to right with a stack, popping the top while the incoming digit is larger and the digits left in the array can still fill length i. Keep at most i digits.
- Compute sub2 = maxSubsequence(nums2, k - i) the same way.
- Compute merged = merge(sub1, sub2): repeatedly take the front digit of whichever sequence has the lexicographically larger remaining suffix.
- Update the best result if merged is larger.
- Return the best result.
Visualization and Code
Loading animation...
- Time Complexity: O(k * (m + n + k^2)), which is O(k(m + n) + k^3). There are at most min(m, n, k) + 1 valid splits. Each split runs maxSubsequence in O(m) and O(n), and the merge makes k decisions where each suffix comparison can cost O(k), so a single merge is O(k^2) in the worst case.
- Space Complexity: O(k). The stack in maxSubsequence uses O(t) space where t <= k. The merged and best result arrays each use O(k) space.