> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0321-create-maximum-number.md).

# 0321. Create Maximum Number

<https://leetcode.com/problems/create-maximum-number>

## Description

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`

## ac

```java
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length, len2 = nums2.length;
        if (len1 > len2) return maxNumber(nums2, nums1, k);
        if (len1 + len2 == k) return merge(nums1, nums2);
        
        int[] max = new int[k];
        for (int i = 0; i <= k && i <= len1; i++) {
            int[] selected1 = selectNums(nums1, i);
            int[] selected2 = selectNums(nums2, k - i);
            int[] mergedArray = merge(selected1, selected2);
            if (isGreater(mergedArray, 0, max, 0)) {
                max = mergedArray;
            }
        }
        
        return max;
    }
    
    private boolean isGreater(int[] nums1, int start1, int[] nums2, int start2) {
        int len1 = nums1.length, len2 = nums2.length;
        int i1 = start1, i2 = start2;
        while (i1 < len1 && i2 < len2) {
            if (nums1[i1] > nums2[i2]) return true;
            if (nums1[i1] < nums2[i2]) return false;
            i1++;
            i2++;
        }
        
        // Lexicographical smaller: [1,2,3,4] is greater than [1,2,3]
        return i1 < len1; 
    }
    
    private int[] merge(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[] res = new int[len1 + len2];
        int index = 0;
        int i1 = 0, i2 = 0;
        while (i1 < len1 && i2 < len2) {
            if (isGreater(nums1, i1, nums2, i2)) {
                res[index] = nums1[i1];
                i1++;
            } else {
                res[index] = nums2[i2];
                i2++;
            }
            index++;
        }
        
        while (i1 < len1) res[index++] = nums1[i1++];
        while (i2 < len2) res[index++] = nums2[i2++];
        
        return res;
    }
     
    private int[] selectNums(int[] nums, int n) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && stack.peek() < nums[i] && isRemainingSufficient(nums, n, i, stack)) {
                stack.pop();
            }
            if (stack.size() < n) stack.push(nums[i]);
        }
        
        return stackToArray(stack);
    }
    
    private boolean isRemainingSufficient(int[] nums, int n, int i, Deque<Integer> stack) {
        return nums.length - i > n - stack.size();
    }
    
    private int[] stackToArray(Deque<Integer> stack) {
        int[] res = new int[stack.size()];
        int i = res.length - 1;
        while (!stack.isEmpty()) {
            res[i--] = stack.pop();
        }
        return res;
    }
}

// O(k(MN)) time, O(N) space;
// 
```

```java
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        // edge cases

        int n1 = nums1.length;
        int n2 = nums2.length;
        int[] maxArray = new int[k];
        for (int i = Math.max(0, k-n2); i <= k && i <= n1; i++) {
            int[] arr1 = selectK(nums1, i);
            int[] arr2 = selectK(nums2, k-i);
            int[] mergeArr = merge(arr1, arr2);
            if (isGreater(mergeArr, 0, maxArray, 0)) {
                maxArray = mergeArr;
            }
        }

        return maxArray;
    }
    private int[] merge(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[] res = new int[n1+n2];
        int i = 0, i1 = 0, i2 = 0;
        while (i1 < n1 && i2 < n2) {
            res[i++] = isGreater(nums1, i1, nums2, i2) ? nums1[i1++] : nums2[i2++];
        }
        while (i1 < n1) res[i++] = nums1[i1++];
        while (i2 < n2) res[i++] = nums2[i2++];
        return res;
    }
    private boolean isGreater(int[] nums1, int i1, int[] nums2, int i2) {
        while (i1 < nums1.length && i2 < nums2.length) {
            if (nums1[i1] > nums2[i2]) return true;
            if (nums1[i1] < nums2[i2]) return false;
            i1++; i2++;
        }
        if (i1 < nums1.length) return true;
        else return false;
    }
    private int[] selectK(int[] nums, int k) {
        int[] res = new int[k];
        Stack<Integer> stack = new Stack<>();
        int i = 0, delete = nums.length - k;
        for (int j = 0; j < nums.length; j++) {
            while (i > 0 && nums[j] > res[i-1] && nums.length - j + i > k) i--;
            if (i < res.length) res[i++] = nums[j];
        }
        return res;
    }
}

/*
1) select k element from array; 2) merge two array, careful lexicographical greater; 3) compare with max.
*/
```