Last updated on January 14th, 2025 at 06:21 am
Here, we see a Create Maximum Number LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, Greedy
Companies
Level of Question
Hard
Create Maximum Number LeetCode Solution
Table of Contents
1. Problem Statement
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]
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Greedy Algorithm with Merging”. This pattern involves selecting the best possible option at each step (greedy choice) to construct the maximum number. Additionally, the merging of two arrays is performed in a way that ensures the lexicographically largest result.
3. Code Implementation in Different Languages
3.1 Create Maximum Number C++
class Solution {
public: vector < int > maxNumber(vector < int > & nums1, vector < int > & nums2, int k) {
int n1 = nums1.size(), n2 = nums2.size();
vector < int > best;
for (int k1 = max(k - n2, 0); k1 <= min(k, n1); ++k1)
best = max(best, maxNumber(maxNumber(nums1, k1),
maxNumber(nums2, k - k1)));
return best;
}
vector < int > maxNumber(vector < int > nums, int k) {
int drop = nums.size() - k;
vector < int > out;
for (int num: nums) {
while (drop && out.size() && out.back() < num) {
out.pop_back();
drop--;
}
out.push_back(num);
}
out.resize(k);
return out;
}
vector < int > maxNumber(vector < int > nums1, vector < int > nums2) {
vector < int > out;
while (nums1.size() + nums2.size()) {
vector < int > & now = nums1 > nums2 ? nums1 : nums2;
out.push_back(now[0]);
now.erase(now.begin());
}
return out;
}
};
3.2 Create Maximum Number Java
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int m = nums2.length;
int[] ans = new int[k];
for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
if (greater(candidate, 0, ans, 0)) ans = candidate;
}
return ans;
}
private int[] merge(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
for (int i = 0, j = 0, r = 0; r < k; ++r)
ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
return ans;
}
public boolean greater(int[] nums1, int i, int[] nums2, int 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]);
}
public int[] maxArray(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[k];
for (int i = 0, j = 0; i < n; ++i) {
while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
if (j < k) ans[j++] = nums[i];
}
return ans;
}
}
3.3 Create Maximum Number JavaScript
var maxNumber = function(nums1, nums2, k) {
const maxArray = (nums, k) => {
const stack = [];
let popCount = nums.length - k;
for (const num of nums) {
while (popCount > 0 && stack.length && stack[stack.length - 1] < num) {
stack.pop();
popCount--;
}
stack.push(num);
}
return stack.slice(0, k);
};
const mergeArrays = (arr1, arr2) => {
const merged = [];
while (arr1.length || arr2.length) {
const bigger = arr1 > arr2 ? arr1 : arr2;
merged.push(bigger.shift());
}
return merged;
};
let max = [];
for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
const merged = mergeArrays(maxArray(nums1, i), maxArray(nums2, k - i));
if (merged > max) max = merged;
}
return max;
};
3.4 Create Maximum Number Python
class Solution(object):
def maxNumber(self, nums1, nums2, k):
def prep(nums, k):
drop = len(nums) - k
out = []
for num in nums:
while drop and out and out[-1] < num:
out.pop()
drop -= 1
out.append(num)
return out[:k]
def merge(a, b):
return [max(a, b).pop(0) for _ in a + b]
return max(
merge(prep(nums1, i), prep(nums2, k - i))
for i in range(k + 1)
if i <= len(nums1) and k - i <= len(nums2)
)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(k * (n1 + n2) + k2) | O(k) |
| Java | O(k * (n1 + n2) + k2) | O(k) |
| JavaScript | O(k * (n1 + n2) + k2) | O(k) |
| Python | O(k * (n1 + n2) + k2) | O(k) |
where n1 and n2 are two arrays and k is lexicographically the largest number of length.
- The dominant term in the time complexity is O(k * (n1 + n2), as k2 is generally smaller for practical values of k.
- The space complexity is linear in k, as the stack and merged arrays are proportional to k.
- The algorithm is efficient for moderate values of k, n1, and n2, but may become computationally expensive for very large inputs.