# Create Maximum Number
**Difficulty:** HARD
[External](https://leetcode.com/problems/create-maximum-number)
Canonical: https://scaleengineer.com/dsa/problems/create-maximum-number
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
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.length`
* `n == nums2.length`
* `1 <= m, n <= 500`
* `0 <= nums1[i], nums2[i] <= 9`
* `1 <= k <= m + n`
* `nums1` and `nums2` do not have leading zeros.

# Approaches
## Backtracking with Memoization
This approach attempts to solve the problem by building the result number one digit at a time, from left to right, using recursion. A helper function is defined to find the maximum number of a certain length `l` from the remaining portions of the input arrays. To handle the choices for each digit, the function explores different possibilities. Since this leads to many overlapping subproblems, memoization is used to store and retrieve results for previously computed states, defined by the current positions in both arrays and the remaining length required.
**Time:** O(m * n * k * (m + n)). The state space is `m*n*k`. Each state computation involves a search over `m+n` elements. This is computationally infeasible. · **Space:** O(m * n * k) for the memoization table. Given m, n <= 500 and k <= 1000, this is too large.
**Pros:** It represents a direct, albeit naive, recursive formulation of the problem.; Memoization helps avoid re-computation of the same subproblems.
**Cons:** Extremely high time complexity, making it too slow for the given constraints.; Very high space complexity due to the 3D memoization table, which is likely to exceed memory limits.
### Explanation
The core of this method is a recursive function, let's call it `solve(i, j, l)`, which is designed to compute the maximum number of length `l` that can be formed from the subarrays `nums1[i:]` and `nums2[j:]`.

To select the first digit of the result, we can't just pick any digit. We must ensure that enough digits remain in `nums1` and `nums2` to form the rest of the number (length `l-1`). The total number of available digits is `(m-i) + (n-j)`. We can afford to skip `(m-i) + (n-j) - l` digits. This means we can search for our first digit in `nums1[i ... i + d]` and `nums2[j ... j + d]`, where `d` is the number of skippable digits.

We greedily find the largest digit, `max_d`, in these search windows. A complication arises if `max_d` appears at multiple positions. For example, if `nums1[p1] == max_d` and `nums2[q1] == max_d`, we must recursively find out which choice leads to a better overall number. This means we have to compare the results of `d + solve(p1 + 1, j, l - 1)` and `d + solve(i, q1 + 1, l - 1)`.

This recursive branching creates overlapping subproblems, as `solve` might be called with the same `(i, j, l)` arguments through different paths. A 3D DP table `memo[i][j][l]` is used to store the results. However, the size of this table, `m * n * k`, is prohibitively large for the given constraints (`500 * 500 * 1000`).
### Algorithm
- Define a recursive function, say `solve(i, j, l)`, which aims to find the maximum number of length `l` using digits from `nums1` starting at index `i` and `nums2` starting at index `j`.
- To prevent recomputing results for the same state `(i, j, l)`, use a 3D array for memoization, `memo[i][j][l]`.
- The base case for the recursion is when the required length `l` is 0, in which case we return an empty sequence.
- In each recursive call, determine the range of indices to search for the best possible first digit. We can discard a total of `(m-i) + (n-j) - l` digits from the start of the remaining arrays. This defines the search window.
- Find the maximum digit `d` within this valid search window in both `nums1` and `nums2`.
- If this maximum digit `d` is found at multiple positions, we must recursively explore each choice. For each occurrence of `d` at `nums1[p]`, we form a candidate number by prepending `d` to the result of `solve(p + 1, j, l - 1)`. Similarly for occurrences in `nums2`.
- Compare all candidate numbers generated from these recursive calls and select the lexicographically largest one.
- Store this result in the memoization table `memo[i][j][l]` before returning.

## Divide and Conquer with Greedy Merging
A more efficient approach is to use a divide and conquer strategy. The problem of forming a maximum number of length `k` is divided into subproblems: selecting `i` digits from `nums1` and `k-i` digits from `nums2`. We iterate through all valid splits `(i, k-i)`.

For each split, we solve two independent subproblems:
1.  Find the best possible subsequence of length `i` from `nums1`.
2.  Find the best possible subsequence of length `k-i` from `nums2`.

Finding the best subsequence is a classic greedy problem that can be solved in linear time using a stack. After obtaining the two best subsequences, we need to merge them to form the final candidate number. This merge operation is also greedy: at each step, we pick the digit from the subsequence that is lexicographically larger from the current position. Finally, we compare the candidate from each split `i` and keep the overall best one.
**Time:** O(k * (m + n + k^2)) in a loose analysis. The loop runs `k` times. `maxSubsequence` is `O(m+n)`. `merge` can be `O(k^2)` in the worst case due to repeated lookaheads. However, a more careful analysis shows the total complexity is closer to `O(k * (m+n))` for many cases, and feasible for the given constraints. · **Space:** O(k). The space is used to store the subsequences and the candidate results, each of which has a length at most `k`.
**Pros:** It is an efficient and correct algorithm that passes within the time limits for the given constraints.; The problem is neatly decomposed into smaller, reusable subproblems (`maxSubsequence` and `merge`).
**Cons:** The logic, especially for the `merge` function's lookahead comparison, can be complex to get right.; The time complexity analysis is not immediately obvious.
### Explanation
This approach breaks the problem down into three main parts: iterating through all possible compositions, finding the maximum subsequence from a single array, and merging two subsequences.

1.  **Main Loop**: We iterate through `i`, the number of digits to take from `nums1`. The valid range for `i` is `max(0, k - n) <= i <= min(k, m)`. For each `i`, we generate a candidate for the max number and compare it with our current best.

2.  **`maxSubsequence(nums, k)`**: This helper finds the lexicographically largest subsequence of length `k`. It uses a greedy strategy with a stack. For each number in the input array, we decide whether to push it onto our result stack. We pop from the stack if the current number is larger than the top of the stack, and if popping doesn't prevent us from achieving a `k`-length result. This ensures our result is as large as possible from left to right.

3.  **`merge(sub1, sub2)`**: This helper combines two subsequences into the largest possible number. It's similar to a standard merge, but when the leading digits of the remaining subsequences are equal, we must perform a lookahead comparison to decide which subsequence to take from. For example, merging `[6, 7]` and `[6, 0, 4]`, we compare `[6, 7]` and `[6, 0, 4]` as a whole. Since `7 > 0`, `[6, 7]` is larger, so we take the `6` from it first.

Here is the Java implementation:
```java
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int[] bestResult = new int[0];

        for (int i = Math.max(0, k - n); i <= k && i <= m; i++) {
            int[] sub1 = maxSubsequence(nums1, i);
            int[] sub2 = maxSubsequence(nums2, k - i);
            int[] candidate = merge(sub1, sub2);
            if (isGreater(candidate, 0, bestResult, 0)) {
                bestResult = candidate;
            }
        }
        return bestResult;
    }

    private int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        int[] stack = new int[k];
        int len = 0;
        for (int i = 0; i < n; i++) {
            while (len > 0 && stack[len - 1] < nums[i] && (n - i) > (k - len)) {
                len--;
            }
            if (len < k) {
                stack[len++] = nums[i];
            }
        }
        return stack;
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int k = nums1.length + nums2.length;
        int[] ans = new int[k];
        int i = 0, j = 0, r = 0;
        while (r < k) {
            ans[r++] = isGreater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        }
        return ans;
    }

    private boolean isGreater(int[] nums1, int p1, int[] nums2, int p2) {
        while (p1 < nums1.length && p2 < nums2.length && nums1[p1] == nums2[p2]) {
            p1++;
            p2++;
        }
        return p2 == nums2.length || (p1 < nums1.length && nums1[p1] > nums2[p2]);
    }
}
```
### Algorithm
- The main function iterates through all possible numbers of digits `i` to take from `nums1`. The number of digits from `nums2` will then be `k-i`. The loop for `i` runs from `max(0, k - n)` to `min(k, m)`.
- For each `i`, find the lexicographically largest subsequence of length `i` from `nums1`. This is done by a helper function `maxSubsequence`.
- Similarly, find the largest subsequence of length `k-i` from `nums2`.
- Merge the two resulting subsequences into a single candidate array of length `k`. This is done by a helper function `merge`.
- The `merge` function compares the two subsequences element by element. If the current digits are different, it picks the larger one. If they are equal, it must look ahead to see which subsequence is lexicographically greater from the current position onwards.
- Compare the merged candidate with the best result found so far. If the new candidate is larger, update the best result.
- After checking all possible values of `i`, the best result found is the answer.

**`maxSubsequence(nums, k)` Algorithm:**
1. Use a stack-like array `stack` of size `k` to build the result.
2. Iterate through `nums`. For each digit `d`:
   a. While the `stack` is not empty, its top element is smaller than `d`, and we have enough remaining elements in `nums` to still form a `k`-length sequence after popping, pop from the stack.
   b. If the `stack` has space, push `d` onto it.
3. The `stack` will hold the maximum subsequence.

**`merge(sub1, sub2)` Algorithm:**
1. Create a result array `merged` of size `k`.
2. Use two pointers, `p1` for `sub1` and `p2` for `sub2`.
3. In a loop that runs `k` times, compare the remaining parts of `sub1` (from `p1`) and `sub2` (from `p2`) using a helper `isGreater`.
4. Append the digit from the greater subsequence to `merged` and advance its pointer.

# Solutions
### Java

```java
class Solution { public int [] maxNumber ( int [] nums1 , int [] nums2 , int k ) { int m = nums1 . length , n = nums2 . length ; int l = Math . max ( 0 , k - n ), r = Math . min ( k , m ); int [] ans = new int [ k ]; for ( int x = l ; x <= r ; ++ x ) { int [] arr1 = f ( nums1 , x ); int [] arr2 = f ( nums2 , k - x ); int [] arr = merge ( arr1 , arr2 ); if ( compare ( arr , ans , 0 , 0 )) { ans = arr ; } } return ans ; } private int [] f ( int [] nums , int k ) { int n = nums . length ; int [] stk = new int [ k ]; int top = - 1 ; int remain = n - k ; for ( int x : nums ) { while ( top >= 0 && stk [ top ] < x && remain > 0 ) { -- top ; -- remain ; } if ( top + 1 < k ) { stk [++ top ] = x ; } else { -- remain ; } } return stk ; } private int [] merge ( int [] nums1 , int [] nums2 ) { int m = nums1 . length , n = nums2 . length ; int i = 0 , j = 0 ; int [] ans = new int [ m + n ]; for ( int k = 0 ; k < m + n ; ++ k ) { if ( compare ( nums1 , nums2 , i , j )) { ans [ k ] = nums1 [ i ++]; } else { ans [ k ] = nums2 [ j ++]; } } return ans ; } private boolean compare ( int [] nums1 , int [] nums2 , int i , int j ) { if ( i >= nums1 . length ) { return false ; } if ( j >= nums2 . length ) { return true ; } if ( nums1 [ i ] > nums2 [ j ]) { return true ; } if ( nums1 [ i ] < nums2 [ j ]) { return false ; } return compare ( nums1 , nums2 , i + 1 , j + 1 ); } }
```

### CPP

```cpp
class Solution { public: vector < int > maxNumber ( vector < int >& nums1 , vector < int >& nums2 , int k ) { auto f = []( vector < int >& nums , int k ) { int n = nums . size (); vector < int > stk ( k ); int top = - 1 ; int remain = n - k ; for ( int x : nums ) { while ( top >= 0 && stk [ top ] < x && remain > 0 ) { -- top ; -- remain ; } if ( top + 1 < k ) { stk [ ++ top ] = x ; } else { -- remain ; } } return stk ; }; function < bool ( vector < int >& , vector < int >& , int , int ) > compare = [ & ]( vector < int >& nums1 , vector < int >& nums2 , int i , int j ) -> bool { if ( i >= nums1 . size ()) { return false ; } if ( j >= nums2 . size ()) { return true ; } if ( nums1 [ i ] > nums2 [ j ]) { return true ; } if ( nums1 [ i ] < nums2 [ j ]) { return false ; } return compare ( nums1 , nums2 , i + 1 , j + 1 ); }; auto merge = [ & ]( vector < int >& nums1 , vector < int >& nums2 ) { int m = nums1 . size (), n = nums2 . size (); int i = 0 , j = 0 ; vector < int > ans ( m + n ); for ( int k = 0 ; k < m + n ; ++ k ) { if ( compare ( nums1 , nums2 , i , j )) { ans [ k ] = nums1 [ i ++ ]; } else { ans [ k ] = nums2 [ j ++ ]; } } return ans ; }; int m = nums1 . size (), n = nums2 . size (); int l = max ( 0 , k - n ), r = min ( k , m ); vector < int > ans ( k ); for ( int x = l ; x <= r ; ++ x ) { vector < int > arr1 = f ( nums1 , x ); vector < int > arr2 = f ( nums2 , k - x ); vector < int > arr = merge ( arr1 , arr2 ); if ( ans < arr ) { ans = move ( arr ); } } return ans ; } };
```

### Python

```python
class Solution : def maxNumber ( self , nums1 : List [ int ], nums2 : List [ int ], k : int ) -> List [ int ]: def f ( nums : List [ int ], k : int ) -> List [ int ]: n = len ( nums ) stk = [ 0 ] * k top = - 1 remain = n - k for x in nums : while top >= 0 and stk [ top ] < x and remain > 0 : top -= 1 remain -= 1 if top + 1 < k : top += 1 stk [ top ] = x else : remain -= 1 return stk def compare ( nums1 : List [ int ], nums2 : List [ int ], i : int , j : int ) -> bool : if i >= len ( nums1 ): return False if j >= len ( nums2 ): return True if nums1 [ i ] > nums2 [ j ]: return True if nums1 [ i ] < nums2 [ j ]: return False return compare ( nums1 , nums2 , i + 1 , j + 1 ) def merge ( nums1 : List [ int ], nums2 : List [ int ]) -> List [ int ]: m , n = len ( nums1 ), len ( nums2 ) i = j = 0 ans = [ 0 ] * ( m + n ) for k in range ( m + n ): if compare ( nums1 , nums2 , i , j ): ans [ k ] = nums1 [ i ] i += 1 else : ans [ k ] = nums2 [ j ] j += 1 return ans m , n = len ( nums1 ), len ( nums2 ) l , r = max ( 0 , k - n ), min ( k , m ) ans = [ 0 ] * k for x in range ( l , r + 1 ): arr1 = f ( nums1 , x ) arr2 = f ( nums2 , k - x ) arr = merge ( arr1 , arr2 ) if ans < arr : ans = arr return ans
```