C++ 16ms, FASTEST, beats 97%.


  • 103
    C

    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].

    class Solution {
    public:
        #define MIN(a,b) (a<b?a:b)
        #define MAX(a,b) (a>b?a:b)
        // create max number of length t from single non-empty vector
        void getMax(int* num, int& len, int* result, int& t, int& sortedLen)
        {
        	int n, top = 0;
        	result[0] = num[0];
        	const int need2drop = len - t;
        	for (int i = 1; i < len; ++i){
        		n = num[i];
        		while (top >= 0 && result[top] < n && (i - top) <= need2drop) --top; // i - top means already dropped i - top numbers
        		if (i - top > need2drop){
        			sortedLen = MAX(1,top);
        			while (++top < t) result[top] = num[i++];
        			return;
        		}
        		if (++top < t) result[top] = n;
        		else top = t - 1;
        	}
        }
        // create max number of different length from single vector
        void dp(int *num, int len, int&sortedLen, int& minL, int& maxL, int *res, int &k){
        	int  j, *head, *prevhead = res;
        	const int soi = sizeof(int);
        	getMax(num, len, res, maxL,sortedLen);
        	for (int l = maxL; l > MAX(minL,1); --l){
        		head = prevhead + k;
        		memcpy(head, prevhead, l*soi);
        		for (j = sortedLen; j < l; ++j){
        			if (head[j] > head[j - 1]){
        				sortedLen = MAX(1, j - 1);
        				memcpy(head + j - 1, prevhead + j, soi*(l - j));
        				break;
        			}
        		}
        		if (j == l) sortedLen = l;
        		prevhead = head;
        	}
        }
        // merge max number created from single vector
        void merge(int* num1,int len1,int* num2,int len2,int* result,int& resSize){
        	int i = 0, j = 0, k = 0;
        	while (i < resSize){
        		if (j < len1 && k < len2){
        			if (num1[j] > num2[k])
        				result[i++] = num1[j++];
        			else if (num1[j] < num2[k])
        				result[i++] = num2[k++];
        			else{
        				int remaining1 = len1 - j, remaining2 = len2 - k, tmp = num1[j];
        				int flag = memcmp(num1 + j, num2 + k, sizeof(int) * MIN(remaining1, remaining2));
        				flag = (flag == 0 ? (remaining1>remaining2 ? 1 : -1) : flag);
        				int * num = flag > 0 ? num1 : num2;
        				int & cnt = flag > 0 ? j : k;
        				int len = flag > 0 ? len1 : len2;
        				while (num[cnt]==tmp && cnt < len && i<resSize) result[i++] = num[cnt++];
        			}
        		}
        		else if (j < len1) result[i++] = num1[j++];
        		else result[i++] = num2[k++];
        	}
        }
        
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k){
        	int soi = sizeof(int), len1 = nums1.size(), len2 = nums2.size(), step = k*soi;
        	int minL1 = MAX(0, k - len2), maxL1 = MIN(k, len1), minL2 = k - maxL1, maxL2 = k - minL1, range = maxL1 - minL1 + 1;
        	int * res = new int[range * k * 2 + 2 * k], *dp1 = res + k, *dp2 = res + range*k+k, *tmp=res+range*2*k+k;
        	memset(res, 0, step);
        	int sortedLen1 = 1, sortedLen2 = 1;
        	if (len1 == 0 && len2 > 0) getMax(&nums2[0], len2, res, k, sortedLen2);
        	else if (len1 > 0 && len2 == 0) getMax(&nums1[0], len1, res, k, sortedLen2);
        	else if (len1 > 0 && len2 > 0){
        		dp(&nums1[0], len1, sortedLen1, minL1, maxL1, dp1,k);
        		dp(&nums2[0], len2, sortedLen2, minL2, maxL2, dp2,k);
        		if (sortedLen1 + sortedLen2 > k){
        			merge(dp1 + k*(maxL1 - sortedLen1), sortedLen1, dp2 + k*(maxL2 - sortedLen2), sortedLen2, tmp, k);
        			vector<int> resv(tmp, tmp + k);
        			delete[] res;
        			return resv;
        		}
        		for (int i = minL1; i <= maxL1; ++i){
        			merge(dp1+k*(maxL1-i), i, dp2+k*(maxL2-k+i), (k-i), tmp,k);
        			if (memcmp(res, tmp, step) < 0) memcpy(res, tmp, step);
        		}
        	}
        	vector<int> resv(res, res + k);
        	delete[] res;
        	return resv;
        }
    };

  • 2

    Nice explanation of your thought process


  • 8
    X

    Thanks for your detailed explanation! Really like your step by step thinking process and the method of generating maximal number of a specific length without starting over. I rewrite your method below, though it's slower than yours, it seems a little clearer, which might be helpful.

    class Solution {
    public:
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<int> result(k), tmp_result(k);
            vector<vector<int> > max_num1(k + 1), max_num2(k + 1);
            genDP(nums1, max_num1, k);  
            genDP(nums2, max_num2, k);
            for(int i = 0; i <= k; i++) {
                if(max_num1[i].size() + max_num2[k - i].size() < k)
                    continue;
                merge(tmp_result, max_num1, max_num2, i, k);
                if(result.empty() || smaller(result, tmp_result))
                    result = tmp_result;
            }
            return result;
        }
        
    private:
        void genDP(vector<int>& nums, vector<vector<int> >& max_num, int k) {
            int i, start;
            for(start = 0; nums.size() > 0; start = (i == 0 ? 0 : i - 1)) {
                if(nums.size() <= k)
                    max_num[nums.size()] = nums;
                for(i = start; i + 1 < nums.size() && nums[i] >= nums[i + 1]; i++);
                nums.erase(nums.begin() + i);
            }
        }
        
        void merge(vector<int>& tmp_result, vector<vector<int> >& max_num1, vector<vector<int> >& max_num2, int n, int k) {
            int i, j, ii, jj;
            for(i = j = 0; i < max_num1[n].size() && j < max_num2[k - n].size(); ) {
                for(ii = i, jj = j; ii < max_num1[n].size() && jj < max_num2[k - n].size() && max_num1[n][ii] == max_num2[k - n][jj]; ii++, jj++);
                if(jj >= max_num2[k - n].size() || (ii < max_num1[n].size() && max_num1[n][ii] > max_num2[k - n][jj]))
                    tmp_result[i + j] = max_num1[n][i++];
                else
                    tmp_result[i + j] = max_num2[k - n][j++];
            }
            for( ; i < max_num1[n].size(); i++)
                tmp_result[i + j] = max_num1[n][i];
            for( ; j < max_num2[k - n].size(); j++)
                tmp_result[i + j] = max_num2[k - n][j];
        }
        
        bool smaller(vector<int>& result, vector<int>& tmp_result) {
            int i;
            for(i = 0; i < result.size() && result[i] == tmp_result[i]; i++);
            if(i < result.size() && result[i] < tmp_result[i])
                return true;
            return false;
        }
    };

  • 4

    Very brilliant solution, but comments are quite essential in your code since the variables are rather misleading sometimes which dramatically increase the complexity of understanding your code. Maybe you can enclose come to get it clearer. Thanks in advance!


  • 2

    +1 for clear explanation.


  • 0
    E

    Nice optimization techniques. Thanks for sharing!


  • 0
    N

    What a brilliant solution!

    Let's analyze the complexities:

    • To find k arrays of nums1 and nums2 with length from 0 to k:
      • Time: O(n+k)
      • Space: O(k^2)
    • To merge an array of length i with an array of length k-i:
      • Time: O(k)
      • Space: O(k) naively
    • To find the maximum i (with each i, we have to merge)
      • Time: O(k^2)
      • Space: O(k)

    In conclusion, time O(n+k^2), space O(k^2). Please correct me if I am wrong.


  • 0
    T

    @chellya Thanks for sharing. Have a question about optimization item 1. Let's say nums1 = [3, 9], nums2[8, 9], if k = 4, the result should be result = 8939. My understanding according to the optimization 1, if k = 3, the result should be 893 which trims the last digit. However, the right one is 989. I guess I didn't understand your optimization constraint. Can you help me understand it? Thanks


  • 0
    C

    @tashia Thanks for asking. In optimization rule 1, we first create the largest number from each array separately WITHOUT LENGTH CONSTRAINT, and as a result, these numbers we create must be non-strictly decreasing. For your case, we can not apply k=4 directly, since the largest number we can create from nums1 is '9' without length constraint, and also '9' for nums2. Then we say the largest number we can create from these two arrays without length constraint is '99'. The value of k is not a constraint, it should be a result. For your case, k=2. And if we want to get the largest number for k=1. Trim it.


  • 0
    B

    @namxh
    No, the time complexity of the merge is O(k^2), because on each iteration it does a naive full suffix comparison (memcmp).

    So the overall complexity is O(n+m+k^3).

    I have to wonder why OP went through all the trouble of optimizing "create single vector max number" when the cost of computing merge is so significantly worse than that of computing single vector max number in worst case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.