321. Create Maximum Number

Description

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

 

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]

 

Constraints:

• m == nums1.length
• n == nums2.length
• 1 <= m, n <= 500
• 0 <= nums1[i], nums2[i] <= 9
• 1 <= k <= m + n

 

Solutions

Solution: Greedy

• Time complexity: O(k(m+n)²)
• Space complexity: O(m+n)

 

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
const maxNumber = function (nums1, nums2, k) {
  const m = nums1.length;
  const n = nums2.length;
  let result = [];

  const sliceNums = (nums, count) => {
    const result = [];
    let drop = nums.length - count;

    for (const num of nums) {
      while (drop && result.at(-1) < num) {
        result.pop();
        drop -= 1;
      }
      result.push(num);
    }
    return result.slice(0, count);
  };
  const isGreater = (numsA, numsB, a = 0, b = 0) => {
    while (a < numsA.length && b < numsB.length) {
      if (numsA[a] > numsB[b]) return true;
      if (numsA[a] < numsB[b]) return false;
      a += 1;
      b += 1;
    }
    return a < numsA.length;
  };
  const mergeSlice = (numsA, numsB) => {
    const result = [];
    let a = (b = 0);

    while (a < numsA.length || b < numsB.length) {
      isGreater(numsA, numsB, a, b) ? result.push(numsA[a++]) : result.push(numsB[b++]);
    }
    return result;
  };

  for (let count = Math.max(0, k - n); count <= Math.min(m, k); count++) {
    const slice1 = sliceNums(nums1, count);
    const slice2 = sliceNums(nums2, k - count);
    const mergeResult = mergeSlice(slice1, slice2);

    if (isGreater(result, mergeResult)) continue;
    result = mergeResult;
  }
  return result;
};