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

Problem Analysis:

At first, we think of simple version — Given one array, return an array of k digits which is maximum number of length k.

vector<int> maxArray(vector<int>& nums, int k) {
  vector<int> array(k, 0);
  for (int i = 0, j = 0; i < nums.size(); ++i) {
    while (nums.size() - i + j > k && j > 0 && array[j - 1] < nums[i]) --j;
    if (j < k) array[j++] = nums[i];
  }
  return array;
}

Then we merge two arrays into an array of k digits which is maximum number of length k.

vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k) {
  vector<int> array(k, 0);
  for (int i = 0, j = 0, r = 0; r < k; ++r)
    array[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
  return array;
}
bool greater(vector<int>& nums1, int i, vector<int>& nums2, int j) {
  while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
    ++i;
    ++j;
  }
  return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
}

we merge two arrays like merge sort, when nums1[i] == nums2[j], we select whether i or j by continuing to compare later numbers follow the arrays.

Finally, we try different length maxArray of the two arrays to find the final answer.

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
  if (k == 0) return {};
  vector<int> res;
  for (int i = max(0, k - (int)nums2.size()); i <= k && i <= nums1.size(); ++i) {
    vector<int> array1 = maxArray(nums1, i);
    vector<int> array2 = maxArray(nums2, k - i);
    vector<int> data = merge(array1, array2, k);
    if (greater(data, 0, res, 0)) res = data;
  }
  return res;
}

Time Complexity: O(k * (nums1.size() + nums2.size()))

Space Complexity: O(k)

reference: https://web.archive.org/web/20160120093629/http://algobox.org/create-maximum-number/