Leetcode Create Maximum Number problem solution

YASH PAL,

In this Leetcode Create Maximum Number problem solution 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.

Leetcode Create Maximum Number problem solution

Problem solution in Python.

class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        
        l1,l2 = len(nums1),len(nums2)
        rs = []
        
        
        def helper(nums,c_len):
            ans = []
            ln = len(nums)
            for idx,val in enumerate(nums):
                while ans and ans[-1]<val and ln-idx> c_len-len(ans):
                    ans.pop(-1)
                if len(ans)<c_len:
                    ans.append(val)
            return ans
        
        for s1 in range(max(0,k-l2),min(k,l1)+1):
            p1,p2 = helper(nums1,s1),helper(nums2,k-s1)
            rs = max(rs,[max(p1,p2).pop(0) for _ in range(k)])
        return rs

Problem solution in Java.

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        if (k==0) return new int[k];
        if (nums1.length==0){
            return getMaxNumberFromNums(nums2,k);
        }
        if (nums2.length==0){
            return getMaxNumberFromNums(nums1,k);
        }

        int[] maxNum2 = getMaxNumberFromNums(nums2,Math.min(nums2.length,k));

        Deque<int[]> maxNums2 = getMaxNumsForAllLenth(maxNum2,Math.max(k-nums1.length, 0));
        
        
        int[] maxNum1 = getMaxNumberFromNums(nums1,Math.min(nums1.length,k));
        int[] res = new int[k];
        for (int len1 = Math.min(nums1.length,k);len1>=Math.max(k-nums2.length,0);len1--){
            if (len1 < Math.min(nums1.length,k)){
                maxNum1 = getMaxNumWithOneLessLen(maxNum1);
            }
            maxNum2 = maxNums2.pollFirst();
            res = getNewMaxNumber(res,maxNum1,maxNum2);
        }
        return res;
    }

    public int[] getMaxNumberFromNums(int[] nums, int maxNumLen){
        int[] maxNum = new int[maxNumLen];
        int len = nums.length;
        int end = 0;
        for (int i=0;i<len;i++){
            while (end >= 1 && maxNum[end-1] < nums[i] && len - i > maxNumLen - end){
                end--;
            }
            if (end < maxNumLen) maxNum[end++] = nums[i];
        }
        return maxNum;
    }

    public Deque<int[]> getMaxNumsForAllLenth(int[] maxNum, int minLen){
        Deque<int[]> maxNums = new LinkedList<int[]>();
        maxNums.add(maxNum);
        while (maxNum.length>minLen){
            int[] nextNum = getMaxNumWithOneLessLen(maxNum);
            maxNums.addFirst(nextNum);
            maxNum = nextNum;
        }
        return maxNums;
    }

    public int[] getMaxNumWithOneLessLen(int[] maxNum){
        int len = maxNum.length, end = 0;
        int[] nextNum = new int[len-1];
        boolean deleted = false;
        for (int i=0;i<len;i++){
            if (end >= len-1) break;
            if ((i==len-1 || maxNum[i] >= maxNum[i+1]) || deleted){
                nextNum[end++] = maxNum[i];             
            } else {
                deleted = true;
            }               
        }    
        return nextNum;
    }
 
    public int[] getNewMaxNumber(int[] maxNum, int[] part1, int[] part2){
        int[] newNum = new int[maxNum.length];
        int p1 = 0, p2 = 0, index = 0;
        boolean newNumLarger = false;
        while (p1 < part1.length || p2 < part2.length){
            newNum[index] = (greater(part1,p1,part2,p2)) ? part1[p1++] : part2[p2++];
            if (maxNum[index] > newNum[index] && !newNumLarger){
                return maxNum;
            } else if (maxNum[index] < newNum[index]){
                newNumLarger = true;
            }
            index++;
        }
        return newNum;
    }
    
    public boolean greater(int[] part1, int p1, int[] part2, int p2){
        while (p1<part1.length && p2<part2.length && part1[p1]==part2[p2]){
            p1++;
            p2++;
        }
        
        return p2==part2.length || (p1 < part1.length && part1[p1] > part2[p2]);
    }
}

Problem solution in C++.

class Solution {
           public:
     vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> result (k, 0);
        vector<vector<int>> maxNumbers1=maxNumbers(nums1, min(k,(int)nums1.size()));
        vector<vector<int>> maxNumbers2=maxNumbers(nums2, min((int)nums2.size(), k));
        
        for (int i=0; i<=min(k, (int)nums1.size()); i++){
            if (k-i<=min(k,(int)nums2.size())) {
                vector<int> tem=merge(maxNumbers1[(int)maxNumbers1.size()-i-1], maxNumbers2[(int)maxNumbers2.size()-k+i-1]);
                if (less_than(result, tem))
                result=tem;
            }
        }
        
        return result;
    }
    
    bool less_than(vector<int>& Number1, vector<int>& Number2){
        int i=0;
        while (i<Number1.size()){
            if (Number1[i]<Number2[i]) return true;
            else if (Number1[i]>Number2[i]) return false;
            else i++;
        }
        return false;
    }
    
    vector<int> merge(vector<int>& Number1, vector<int>& Number2){
        if (Number1.size()==0) return Number2;
        if (Number2.size()==0) return Number1;
        vector<int> result;
        int i1=0, i2=0;
        while (i1<Number1.size() || i2<Number2.size()){
            if (i2==Number2.size()) {
                result.push_back(Number1[i1]);
                 i1++;
            }else if (i1==Number1.size()){
                result.push_back(Number2[i2]);
                i2++;
            }
            else if (Number1[i1]<Number2[i2]){
                result.push_back(Number2[i2]);
                i2++;
            }else if (Number1[i1]>Number2[i2]){
                result.push_back(Number1[i1]);
                i1++;
            }else {
                int k1=i1, k2=i2;
                while (k1<Number1.size() && k2<Number2.size() && Number1[k1]==Number2[k2]) {k1++; k2++;}
                if (k1==Number1.size() || (k2<Number2.size() && Number2[k2]>Number1[k1])) {
                    result.push_back(Number2[i2]);
                    i2++;
                }else {
                    result.push_back(Number1[i1]);
                    i1++;
                }
            }
        }
        return result;
    }
    
    vector<vector<int>> maxNumbers(vector<int>& nums1, int k){
        vector<vector<int>> result;
        vector<int> Number (nums1.begin(), nums1.begin()+k);
        for (int i=k; i<nums1.size(); i++){
            int j=0;
            while (j+1<k && Number[j]>=Number[j+1]) j++;
            if (j==k-1){
                if (nums1[i]>Number[j]) Number[j]=nums1[i];
            } 
            else {
                Number.erase(Number.begin()+j);
                Number.push_back(nums1[i]);
            }
        }
        result.push_back(Number);
        for (int i=0; i<k; i++){
            int j=0;
            while (j+1<Number.size() && Number[j]>=Number[j+1]) j++;
            Number.erase(Number.begin()+j);
            result.push_back(Number);
        }
        
        return result;
    }
    
    
};

Problem solution in C.

void getMaxNumber(int *nums, int size, int outsize, int *out) {
    int len = 0, i, k = size - outsize;
    out[0] = nums[0];
    for (i = 1; i < size; i++) {
        while (len >= 0 && k > 0 && nums[i] > out[len]) k--, len--;
        out[++len] = nums[i];
    }
}

int compareArr(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int i;
    for (i = 0; i < nums1Size && i < nums2Size && nums1[i] == nums2[i]; i++);
    //if (i == nums1Size && i == nums2Size) return 0;
    if (i == nums1Size) return -1;
    if (i == nums2Size) return 1;
    return (nums1[i] - nums2[i]);
}

void merge(int* nums1, int nums1Size, int* nums2, int nums2Size, int *out) {
    int len = 0, i = 0, j = 0;
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] > nums2[j]) out[len++] = nums1[i++];
        else if (nums1[i] < nums2[j]) out[len++] = nums2[j++];
        else if (compareArr(nums1 + i, nums1Size - i, nums2 + j, nums2Size - j) >= 0) out[len++] = nums1[i++];
        else out[len++] = nums2[j++];
    }
    while (i < nums1Size) out[len++] = nums1[i++];
    while (j < nums2Size) out[len++] = nums2[j++];
}

int compare(int *arr1, int *arr2, int len) {
    int i = 0;
    for (; i < len && arr1[i] == arr2[i]; i++);
    if (i < len) return arr1[i] - arr2[i];
    return 0;
}

int min(int x, int y) {return x <= y ? x: y;}

int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) {
    int i = 0, j = 0;
    int *arr1, *arr2, *ans, *tmp;
    if (k <= 0) {
        *returnSize = 0;
        return NULL;
    }
    arr1 = malloc(sizeof(int) * (nums1Size + nums2Size));
    arr2 = arr1 + nums1Size;
    ans = malloc(sizeof(int) * k);
    tmp = malloc(sizeof(int) * k);
    for (j = 0; j < k; j++) ans[j] = 0;
    for (i = min(k, nums1Size); i >= 0; i--) {
        j = k - i;
        if (j > nums2Size) break;
        if (i > 0) getMaxNumber(nums1, nums1Size, i, arr1);
        if (j > 0) getMaxNumber(nums2, nums2Size, j, arr2);
        merge(arr1, i, arr2, j, tmp);
        if (compare(tmp, ans, k) > 0) {
            for (j = 0; j < k; j++) ans[j] = tmp[j];
        }
    }
    free(tmp);
    free(arr1);
    *returnSize = k; 
    return ans;
}

coding problems