Algorithm
Problem Name: 321. Create Maximum Number
Problem Link: https://leetcode.com/problems/create-maximum-number/
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.lengthn == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + n
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const maxNumber = function(nums1, nums2, k) {
const n = nums1.length
const m = nums2.length
let ans = new Array(k).fill(0)
for (let i = Math.max(0, k - m); i < = k && i <= n; i++) {
const candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k)
if (greater(candidate, 0, ans, 0)) ans = candidate
}
return ans
}
function merge(nums1, nums2, k) {
const ans = new Array(k)
for (let i = 0, j = 0, r = 0; r < k; r++) {
ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++]
}
return ans
}
function greater(nums1, i, nums2, j) {
while (i < nums1.length && j < nums2.length && nums1[i] === nums2[j]) {
i++
j++
}
return j === nums2.length || (i < nums1.length && nums1[i] > nums2[j])
}
function maxArray(nums, k) {
const n = nums.length
const ans = new Array(k)
for (let i = 0, j = 0; i < n; i++) {
while (n - i > k - j && j > 0 && ans[j - 1] < nums[i]) j--
if (j < k) ans[j++] = nums[i]
}
return ans
}
Input
nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output
[9,8,6,5,3]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxNumber(self, nums1, nums2, k):
def merge(arr1, arr2):
res, i, j = [], 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i:] >= arr2[j:]:
res.append(arr1[i])
i += 1
else:
res.append(arr2[j])
j += 1
if i < len(arr1): res += arr1[i:]
elif j < len(arr2): res += arr2[j:]
return res
def makeArr(arr, l):
i, res = 0, []
for r in range(l - 1, -1, -1):
num, i = max(arr[i:-r] or arr[i:])
i = -i + 1
res.append(num)
return res
nums1, nums2, choices = [(num, -i) for i, num in enumerate(nums1)], [(num, -i) for i, num in enumerate(nums2)], []
for m in range(k + 1):
if m > len(nums1) or k - m > len(nums2): continue
arr1, arr2 = makeArr(nums1, m), makeArr(nums2, k - m)
choices.append(merge(arr1, arr2))
return max(choices)
Input
nums1 = [6,7], nums2 = [6,0,4], k = 5
Output
[6,7,6,0,4]