# 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]];
}
};