321. Create Maximum Number (Hard)

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]

Solution:

The basic idea:

To create max number of length k from two arrays, you need to create max number of length i from array one and max number of length k-i from array two, then combine them together. After trying all possible i, you will get the max number created from two arrays.

Optimization:

  1. Suppose nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], the maximum number you can create from nums1 is [6, 5] with length 2. For nums2, it's [9, 8, 3] with length 3. Merging the two sequence, we have [9, 8, 6, 5, 3], which is the max number we can create from two arrays without length constraint. If the required length k<=5, we can simply trim the result to required length from front. For instance, if k=3, then [9, 8, 6] is the result.

  2. Suppose we need to create max number with length 2 from num = [4, 5, 3, 2, 1, 6, 0, 8]. The simple way is to use a stack, first we push 4 and have stack [4], then comes 5 > 4, we pop 4 and push 5, stack becomes [5], 3 < 5, we push 3, stack becomes [5, 3]. Now we have the required length 2, but we need to keep going through the array in case a larger number comes, 2 < 3, we discard it instead of pushing it because the stack already grows to required size 2. 1 < 3, we discard it. 6 > 3, we pop 3, since 6 > 5 and there are still elements left, we can continue to pop 5 and push 6, the stack becomes [6], since 0 < 6, we push 0, the stack becomes [6, 0], the stack grows to required length again. Since 8 > 0, we pop 0, although 8 > 6, we can't continue to pop 6 since there is only one number, which is 8, left, if we pop 6 and push 8, we can't get to length 2, so we push 8 directly, the stack becomes [6, 8].

  3. In the basic idea, we mentioned trying all possible length i. If we create max number for different i from scratch each time, that would be a waste of time. Suppose num = [4, 9, 3, 2, 1, 8, 7, 6], we need to create max number with length from 1 to 8. For i==8, result is the original array. For i==7, we need to drop 1 number from array, since 9 > 4, we drop 4, the result is [9, 3, 2, 1, 8, 7, 6]. For i==6, we need to drop 1 more number, 3 < 9, skip, 2 < 3, skip, 1 < 2, skip, 8 > 1, we drop 1, the result is [9, 3, 2, 8, 7, 6]. For i==5, we need to drop 1 more, but this time, we needn't check from beginning, during last scan, we already know [9, 3, 2] is monotonically non-increasing, so we check 8 directly, since 8 > 2, we drop 2, the result is [9, 3, 8, 7, 6]. For i==4, we start with 8, 8 > 3, we drop 3, the result is [9, 8, 7, 6]. For i==3, we start with 8, 8 < 9, skip, 7 < 8, skip, 6 < 7, skip, by now, we've got maximum number we can create from num without length constraint. So from now on, we can drop a number from the end each time. The result is [9, 8, 7], For i==2, we drop last number 7 and have [9, 8]. For i==1, we drop last number 8 and have [9].

version 1: 36ms

class Solution {
    void DP(vector<int>& nums, vector<vector<int>>& dp, int s, int t) {
        int len = nums.size();
        for (int i = len, j = 0; i >= s; --i) { // i current length
            if (i <= t) dp[i] = nums;
            // remove one digit in each iteration
            for (j = max(0, j-1) ; j+1 < i && nums[j] >= nums[j+1]; ++j);
            nums.erase(nums.begin()+j);
        }
    }

    vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
        int i1 = 0, i2 = 0, j1 = 0, j2 = 0, len1 = nums1.size(), len2 = nums2.size();
        vector<int> res;
        while (i1 < len1 && i2 < len2) {
            j1 = i1; j2 = i2;
            while (j1 < len1 && j2 < len2 && nums1[j1] == nums2[j2]) { ++j1; ++j2;}
            if (j2 >= len2 || (j1 < len1 && nums1[j1] > nums2[j2])) res.push_back(nums1[i1++]);
            else res.push_back(nums2[i2++]);
        }
        while (i1 < nums1.size()) res.push_back(nums1[i1++]);
        while (i2 < nums2.size()) res.push_back(nums2[i2++]);
        return res;
    }

public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int len1 = nums1.size(), len2 = nums2.size();
        vector<vector<int>> dp1(k+1), dp2(k+1);
        DP(nums1, dp1, max(1, k-len2), min(k, len1));
        DP(nums2, dp2, max(1, k-len1), min(k, len2));

        vector<int> res;
        for (int i = max(0, k-len2); i <= min(k, len1); ++i) {
            vector<int> tmp = merge(dp1[i], dp2[k-i]);
            res = max(res, tmp);
        }
        cout << res.size();
        return res;
    }
};

improved version 2: 29ms

isBigger: check if the current number is smaller than res. If smaller, no need to keep checking

class Solution {
    void DP(vector<int>& nums, vector<vector<int>>& dp, int s, int t) {
        int len = nums.size();
        for (int i = len, j = 0; i >= s; --i) { // i current length
            if (i <= t) dp[i] = nums;
            // remove one digit in each iteration
            for (j = max(0, j-1) ; j+1 < i && nums[j] >= nums[j+1]; ++j);
            nums.erase(nums.begin()+j);
        }

    }

    void merge(vector<int>& nums1, vector<int>& nums2, vector<int>& res) {
        int len1 = nums1.size(), len2 = nums2.size();
        int i = 0, i1 = 0, i2 = 0, j1 = 0, j2 = 0;
        bool isBigger = false;
        while (i1 < len1 && i2 < len2) {
            j1 = i1; j2 = i2;
            while (j1 < len1 && j2 < len2 && nums1[j1] == nums2[j2]) { ++j1; ++j2;}
            if (j2 >= len2 || (j1 < len1 && nums1[j1] > nums2[j2])) {
                if (isBigger) res[i++] = nums1[i1++];
                else {
                    if (nums1[i1] < res[i]) return;
                    if (nums1[i1] > res[i]) isBigger = true;
                    res[i++] = nums1[i1++];
                }
            }
            else {
                if (isBigger) res[i++] = nums2[i2++];
                else {
                    if (nums2[i2] < res[i]) return;
                    if (nums2[i2] > res[i]) isBigger = true;
                    res[i++] = nums2[i2++];
                }
            }

        }
        while (i1 < nums1.size()) {
            if (isBigger) res[i++] = nums1[i1++];
            else {
                if (nums1[i1] < res[i]) return;
                if (nums1[i1] > res[i]) isBigger = true;
                res[i++] = nums1[i1++];
            }
        }
        while (i2 < nums2.size()) {
            if (isBigger) res[i++] = nums2[i2++];
            else {
                if (nums2[i2] < res[i]) return;
                if (nums2[i2] > res[i]) isBigger = true;
                res[i++] = nums2[i2++];
            }
        }
    }

public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int len1 = nums1.size(), len2 = nums2.size();
        vector<vector<int>> dp1(k+1), dp2(k+1);
        DP(nums1, dp1, max(1, k-len2), min(k, len1));
        DP(nums2, dp2, max(1, k-len1), min(k, len2));

        vector<int> res(k, 0);
        for (int i = max(0, k-len2); i <= min(k, len1); ++i) {
            merge(dp1[i], dp2[k-i], res);
        }

        return res;
    }
};

results matching ""

    No results matching ""