Build the Largest Number by Merging Two Digit Sequences
Solve this Problemnums1 and nums2, and an integer k, choose some digits from each (preserving each array's own relative order) so that the total number chosen is exactly k, then interleave the two chosen sequences (again preserving each side's relative order) to form the largest possible k-digit number.
This combines two ideas already seen separately in this topic. First, extracting the largest length-m subsequence from a single array is the same monotonic-stack technique used for "smallest value after deleting digits" — just with the comparison flipped to keep bigger digits instead of smaller ones. Second, merging two already-chosen sequences into the largest possible interleaving is a greedy digit-by-digit comparison: at each step, take from whichever side's remaining sequence would form the larger continuation if compared digit by digit (falling back to whichever side is longer if one is a genuine prefix of the other). Trying every valid split of k between the two arrays and keeping the best merged result ties it all together.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums1.length, nums2.length ≤ 4 - ◆
0 ≤ nums1[i], nums2[i] ≤ 9 (single decimal digits) - ◆
1 ≤ k ≤ nums1.length + nums2.length
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Naive Rescan-Based Subsequence Extraction
BruteTry every way to split k between the two arrays: taking i digits from nums1 and k−i from nums2, for every valid i. For each split, extract the largest possible length-i subsequence from an array by repeatedly scanning for the first digit immediately followed by something bigger (removing it, since a smaller digit blocking a bigger one is always wasteful) and restarting the scan from the beginning after every removal — an O(n²)-per-array technique. Merge the two chosen subsequences by always taking whichever side's next remaining digits form the (lexicographically) larger continuation, and keep the best merged result across every split tried.
O((n+m)² · k)O(n+m)1class Solution {
2 public int[] maxNumberFromTwoArrays(int[] nums1, int[] nums2, int k) {
3 int n1 = nums1.length, n2 = nums2.length;
4 int[] best = null;
5 int start = Math.max(0, k - n2);
6 int end = Math.min(k, n1);
7 for (int i = start; i <= end; i++) {
8 int[] s1 = maxSubsequence(nums1, i);
9 int[] s2 = maxSubsequence(nums2, k - i);
10 int[] merged = merge(s1, s2);
11 if (best == null || greater(merged, 0, best, 0)) {
12 best = merged;
13 }
14 }
15 return best;
16 }
17
18 private int[] maxSubsequence(int[] nums, int k) {
19 List<Integer> arr = new ArrayList<>();
20 for (int x : nums) arr.add(x);
21 int toDrop = arr.size() - k;
22 while (toDrop > 0) {
23 int i = 0;
24 while (i < arr.size() - 1 && arr.get(i) >= arr.get(i + 1)) i++;
25 arr.remove(i);
26 toDrop--;
27 }
28 int[] result = new int[arr.size()];
29 for (int i = 0; i < arr.size(); i++) result[i] = arr.get(i);
30 return result;
31 }
32
33 private int[] merge(int[] a, int[] b) {
34 int[] result = new int[a.length + b.length];
35 int i = 0, j = 0, idx = 0;
36 while (i < a.length || j < b.length) {
37 if (greater(a, i, b, j)) {
38 result[idx++] = a[i++];
39 } else {
40 result[idx++] = b[j++];
41 }
42 }
43 return result;
44 }
45
46 private boolean greater(int[] a, int i, int[] b, int j) {
47 while (i < a.length && j < b.length) {
48 if (a[i] != b[j]) return a[i] > b[j];
49 i++; j++;
50 }
51 return (a.length - i) > (b.length - j);
52 }
53}Optimal — Monotonic Stack Subsequence Extraction
OptimalSame overall strategy — try every split, extract the best length-i and length-(k−i) subsequence from each array, merge them, and keep the winner — but replace the naive rescan with a single-pass monotonic stack: walk each array once, popping a smaller digit off the top whenever a bigger one arrives and there's still budget to drop, then push the current digit. This is the same "next-greater" idea used throughout this topic, applied to build a subsequence instead of comparing neighbors. Extracting each candidate subsequence drops from O(n²) to O(n), so the whole algorithm's cost is dominated by the number of splits times a linear scan, instead of a quadratic one.
O((n+m) · min(n,m))O(n+m)1class Solution {
2 public int[] maxNumberFromTwoArrays(int[] nums1, int[] nums2, int k) {
3 int n1 = nums1.length, n2 = nums2.length;
4 int[] best = null;
5 int start = Math.max(0, k - n2);
6 int end = Math.min(k, n1);
7 for (int i = start; i <= end; i++) {
8 int[] s1 = maxSubsequence(nums1, i);
9 int[] s2 = maxSubsequence(nums2, k - i);
10 int[] merged = merge(s1, s2);
11 if (best == null || greater(merged, 0, best, 0)) {
12 best = merged;
13 }
14 }
15 return best;
16 }
17
18 private int[] maxSubsequence(int[] nums, int k) {
19 int[] stack = new int[nums.length];
20 int top = -1;
21 int toDrop = nums.length - k;
22 for (int x : nums) {
23 while (top >= 0 && toDrop > 0 && stack[top] < x) {
24 top--;
25 toDrop--;
26 }
27 stack[++top] = x;
28 }
29 int[] result = new int[k];
30 for (int i = 0; i < k; i++) result[i] = stack[i];
31 return result;
32 }
33
34 private int[] merge(int[] a, int[] b) {
35 int[] result = new int[a.length + b.length];
36 int i = 0, j = 0, idx = 0;
37 while (i < a.length || j < b.length) {
38 if (greater(a, i, b, j)) {
39 result[idx++] = a[i++];
40 } else {
41 result[idx++] = b[j++];
42 }
43 }
44 return result;
45 }
46
47 private boolean greater(int[] a, int i, int[] b, int j) {
48 while (i < a.length && j < b.length) {
49 if (a[i] != b[j]) return a[i] > b[j];
50 i++; j++;
51 }
52 return (a.length - i) > (b.length - j);
53 }
54}