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

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;
// 

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.
*/