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:
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.
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].
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;
}
};