Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

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

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

The idea is to use Greedy approach. If we choose i numbers from the first array, then we need another k - i numbers from the second array. So we go through each number combination, for each array with desired number of elements, we find the largest sub array we can get. Then we use a merge sort like approach to merge get the maximum array from the two arrays, and compare with the last result. Note that different from merge sort, not only do we need to compare the current elements, we need to compare all subsequent elements, i.e., we need to get the larger number constructed by the array starting from current element. For i, if the length of the second array is less than k, then we need at least k - nums2.length elements from the first array.

public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] rst = new int[k];
        int len1 = nums1.length;
        int len2 = nums2.length;
        for (int i = Math.max(k - len2, 0); i <= Math.min(len1, k); i++) {
            int[] currGreatest1 = getLargest(nums1, i);
            int[] currGreatest2 = getLargest(nums2, k - i);

            int[] currResult = new int[k];
            int pos = 0, n1 = 0, n2 = 0;
            while (n1 < currGreatest1.length || n2 < currGreatest2.length) {
                currResult[pos++] = isGreater(currGreatest1, n1, currGreatest2, n2) ? currGreatest1[n1++] : currGreatest2[n2++];
            }
            if (isGreater(currResult, 0, rst, 0)) {
                rst = currResult;
            }
            
        }
        return rst;
    }

    private boolean isGreater(int[] first, int start1, int[] second, int start2) {
        int n1 = start1, n2 = start2;
        while (n1 < first.length && n2 < second.length) {
            if (first[n1] > second[n2]) {
                return true;
            } else if (first[n1] < second[n2]) {
                return false;
            }
            n1++;
            n2++;
        }
        return n1 < first.length;
    }

    private int[] getLargest(int[] nums1, int length) {
        int len = nums1.length;
        int[] rst = new int[length];

        int pos = 0;
        for (int i = 0; i < len; i++) {
            while (pos > 0 && pos + len - i - 1 >= length &&rst[pos - 1] < nums1[i]) {
                pos--;
            }
            if (pos < length) {
                rst[pos++] = nums1[i];

            }

        }
        return rst;
    }