# 321. 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.

Note: You should try to optimize your time and space complexity.

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]

# Solution

Approach 1: Backtracing (Time Limit Exceeded w/o memo; Memory Limit Exceeded w/ memo).

Approach 2: Divde and conquer.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Divde and conquer.
class Solution {
private:
    int cmpMaxVector(vector<int>& v1, int head1, vector<int>& v2, int head2) {
        int n1 = v1.size();
        int n2 = v2.size();
        int i1 = head1;
        int i2 = head2;
        while (i1 < n1 || i2 < n2)
        {
            if (i2 >= n2 || i1 < n1 && v1[i1] > v2[i2])
                return 1;
            else if (i1 >= n1 || i2 < n2 && v1[i1] < v2[i2])
                return -1;
            i1++;
            i2++;
        }
        return 0;
    }
    vector<int> getMaxNumber(vector<int>& nums, int k) {
        vector<int> res(k, 0);
        int j = 0;
        if (k == 0)
            return res;
        for (int i = 0; i < nums.size(); ++i)
        {
            while (j > 0 && res[j-1] < nums[i] && j + nums.size() - i - 1 >= k)
                j--;
            if (j < k)
                res[j++] = nums[i];
        }
        return res;
    }
    vector<int> mergeMaxNumber(vector<int>& v1, vector<int>& v2) {
        vector<int> res;
        int n1 = v1.size();
        int n2 = v2.size();
        int i1 = 0;
        int i2 = 0;
        while (i1 < n1 || i2 < n2)
        {
            if (i2 >= n2 || i1 < n1 && v1[i1] > v2[i2])
            {
                res.push_back(v1[i1]);
                i1++;
            }
            else if (i1 >= n1 || i2 < n2 && v1[i1] < v2[i2])
            {
                res.push_back(v2[i2]);
                i2++;
            }
            else if (cmpMaxVector(v1, i1+1, v2, i2+1) >= 0) // tricky.
            {
                res.push_back(v1[i1]);
                i1++;
            }
            else
            {
                res.push_back(v2[i2]);
                i2++;
            }
        }
        return res;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<int> res;
        for (int len1 = 0; len1 <= k; ++len1)
        {
            int len2 = k - len1;
            if (len1 <= nums1.size() && len2 <= nums2.size())
            {
                vector<int> tmp1 = getMaxNumber(nums1, len1);
                vector<int> tmp2 = getMaxNumber(nums2, len2);
                vector<int> tmp = mergeMaxNumber(tmp1, tmp2);
                if (res.size() == 0 || cmpMaxVector(res, 0, tmp, 0) < 0)
                    res = tmp;
            }
        }
        return res;
    }
};

Approach 2:

// Time Limit Exceeded w/o memo.
// Memory Limit Exceeded w/ memo.
class Solution {
private:
    int getMaxIdx(vector<int>& nums, int head, int tail) {
        if (head < 0 || tail >= nums.size() || head > tail)
            return -1;
        int maxIdx = head;
        for (int i = head+1; i <= tail; ++i)
        {
            if (nums[i] > nums[maxIdx])
                maxIdx = i;
        }
        return maxIdx;
    }
    int getMaxVector(vector<int> v1, vector<int> v2) {
        for (int i = 0; i < v1.size(); ++i)
        {
            if (v1[i] > v2[i])
                return 1;
            else if (v1[i] < v2[i])
                return -1;
        }
        return 0;
    }
    void doMaxNumber(
            vector<int>& nums1, int head1,
            vector<int>& nums2, int head2,
            int k, vector<vector<int>>& res, vector<vector<int>>& buf)
    {
        if (k <= 0)
        {
            buf.push_back(vector<int>());
            res[head1][head2] = buf.size() - 1;
            return;
        }
        if (res[head1][head2] >= 0)
            return;
        int tail1 = nums1.size() - 1;
        int tail2 = nums2.size() - 1;
        int n1 = tail1 - head1 + 1;
        int n2 = tail2 - head2 + 1;
        int m1 = getMaxIdx(nums1, head1, (k<=n2) ? tail1 : tail1-(k-n2)+1);
        int m2 = getMaxIdx(nums2, head2, (k<=n1) ? tail2 : tail2-(k-n1)+1);
        if (m2 < 0 || m1 >= 0 && nums1[m1] > nums2[m2])
        {
            doMaxNumber(nums1, m1+1, nums2, head2, k-1, res, buf);
            buf.push_back(buf[res[m1+1][head2]]);
            buf.back().insert(buf.back().begin(), nums1[m1]);
        }
        else if (m1 < 0 || m2 >= 0 && nums1[m1] < nums2[m2])
        {
            doMaxNumber(nums1, head1, nums2, m2+1, k-1, res, buf);
            buf.push_back(buf[res[head1][m2+1]]);
            buf.back().insert(buf.back().begin(), nums2[m2]);
        }
        else if (m1 >= 0 && m2 >= 0 && nums1[m1] == nums2[m2])
        {
            doMaxNumber(nums1, m1+1, nums2, head2, k-1, res, buf);
            doMaxNumber(nums1, head1, nums2, m2+1, k-1, res, buf);
            if (getMaxVector(buf[res[m1+1][head2]], buf[res[head1][m2+1]]) >= 0)
            {
                buf.push_back(buf[res[m1+1][head2]]);
                buf.back().insert(buf.back().begin(), nums1[m1]);
            }
            else
            {
                buf.push_back(buf[res[head1][m2+1]]);
                buf.back().insert(buf.back().begin(), nums2[m2]);
            }
        }
        res[head1][head2] = buf.size() - 1;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<vector<int>> res = vector<vector<int>>(n1+1, vector<int>(n2+1, -1));
        vector<vector<int>> buf;
        doMaxNumber(nums1, 0, nums2, 0, k, res, buf);
        return buf[res[0][0]];
    }
};