Leetcode 321: Create Maximum Number

https://leetcode.com/problems/create-maximum-number/description/

Notes:

This question is hard question, as labeled.

My first method is using memorization, memo[i][j][k] represents the largest new arr with size of k by using elements starting of i-th in arr1 and j-th in arr2. But it quickly receive TLE.

It turns out it can be solved greedily. After decomposing it into two simpler sub-problems, this question becomes not that hard.

1): find a largest subsequence with a size of k from a given array;

2): merge two given arrays to form the largest sequence (including all elements).

Both sub-questions above are not hard to implemented (maybe the second one need to deal with a specific case when the first elements are equal, but it is still not hard to deal with with a short comparison function, see below).

See the code below:

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> res(k);
        for(int i=max(0, k-n); i<=min(k, m); ++i) {
            vector<int> v1 = find(nums1, i), v2 = find(nums2, k-i);
                                          //find i from nums1, find (k-i) from nums2
            vector<int> nt = merge(v1, v2);
            if(larger(nt, 0, res, 0)) res = nt;
        }
        return res;
    }

private:
    vector<int> find(vector<int> &v, int k) {//find largest sequence with k elements;
        vector<int> res(k);
        int len = v.size();
        for(int i=0, j=0; i<len; ++i) {
            while(len-i+j>k && j>0 && res[j-1] < v[i]) --j;
            if(j<k) res[j++] = v[i];
        }
        return res;
    }

    bool larger(vector<int> &v1, int i, vector<int> &v2, int j) {//very useful comp function
        while(i<v1.size() && j<v2.size() && v1[i] == v2[j]) {
            ++i;
            ++j;
        }
        return j == v2.size() || (i < v1.size() && v1[i] > v2[j]);
    }

    vector<int> merge(vector<int> &v1, vector<int> &v2) {//merge two arrays into the largest one;
        int m = v1.size(), n = v2.size();
        vector<int> res(m+n);
        for(int i=0, j=0, k = 0; i<v1.size() || j <v2.size(); ++k) {
            res[k] = larger(v1, i, v2, j) ? v1[i++] : v2[j++];
        }
        return res;
    } 
};

There is another way to implement the find (vector<int>, int) function.

vector<int> find(vector<int> &v, int k) {//find k elements which gives the largest value;
        vector<int> res(k);
        int len = v.size();
        if(!k && len < k) return res;
        if(len == k) return v;
        int left = 0, right = len - k, i = 0;
        while(i < k) {
            int idMax = left;//initialization
            for(int i=left; i<=right; ++i) {
                if(v[i] > v[idMax]) idMax = i;
            }
            res[i++] = v[idMax];
            left = idMax + 1;//shift search range
            ++right;
        }
        return res;
    }

Follow-up: all the questions can be converted into finding the largest string sequence with strings.