# Leetcode Create Maximum Number problem solution

In this Leetcode Create Maximum Number problem solution 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.

## Problem solution in Python.

```class Solution(object):
def maxNumber(self, nums1, nums2, k):

l1,l2 = len(nums1),len(nums2)
rs = []

def helper(nums,c_len):
ans = []
ln = len(nums)
for idx,val in enumerate(nums):
while ans and ans[-1]<val and ln-idx> c_len-len(ans):
ans.pop(-1)
if len(ans)<c_len:
ans.append(val)
return ans

for s1 in range(max(0,k-l2),min(k,l1)+1):
p1,p2 = helper(nums1,s1),helper(nums2,k-s1)
rs = max(rs,[max(p1,p2).pop(0) for _ in range(k)])
return rs
```

## Problem solution in Java.

```public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
if (k==0) return new int[k];
if (nums1.length==0){
return getMaxNumberFromNums(nums2,k);
}
if (nums2.length==0){
return getMaxNumberFromNums(nums1,k);
}

int[] maxNum2 = getMaxNumberFromNums(nums2,Math.min(nums2.length,k));

Deque<int[]> maxNums2 = getMaxNumsForAllLenth(maxNum2,Math.max(k-nums1.length, 0));

int[] maxNum1 = getMaxNumberFromNums(nums1,Math.min(nums1.length,k));
int[] res = new int[k];
for (int len1 = Math.min(nums1.length,k);len1>=Math.max(k-nums2.length,0);len1--){
if (len1 < Math.min(nums1.length,k)){
maxNum1 = getMaxNumWithOneLessLen(maxNum1);
}
maxNum2 = maxNums2.pollFirst();
res = getNewMaxNumber(res,maxNum1,maxNum2);
}
return res;
}

public int[] getMaxNumberFromNums(int[] nums, int maxNumLen){
int[] maxNum = new int[maxNumLen];
int len = nums.length;
int end = 0;
for (int i=0;i<len;i++){
while (end >= 1 && maxNum[end-1] < nums[i] && len - i > maxNumLen - end){
end--;
}
if (end < maxNumLen) maxNum[end++] = nums[i];
}
return maxNum;
}

public Deque<int[]> getMaxNumsForAllLenth(int[] maxNum, int minLen){
while (maxNum.length>minLen){
int[] nextNum = getMaxNumWithOneLessLen(maxNum);
maxNum = nextNum;
}
return maxNums;
}

public int[] getMaxNumWithOneLessLen(int[] maxNum){
int len = maxNum.length, end = 0;
int[] nextNum = new int[len-1];
boolean deleted = false;
for (int i=0;i<len;i++){
if (end >= len-1) break;
if ((i==len-1 || maxNum[i] >= maxNum[i+1]) || deleted){
nextNum[end++] = maxNum[i];
} else {
deleted = true;
}
}
return nextNum;
}

public int[] getNewMaxNumber(int[] maxNum, int[] part1, int[] part2){
int[] newNum = new int[maxNum.length];
int p1 = 0, p2 = 0, index = 0;
boolean newNumLarger = false;
while (p1 < part1.length || p2 < part2.length){
newNum[index] = (greater(part1,p1,part2,p2)) ? part1[p1++] : part2[p2++];
if (maxNum[index] > newNum[index] && !newNumLarger){
return maxNum;
} else if (maxNum[index] < newNum[index]){
newNumLarger = true;
}
index++;
}
return newNum;
}

public boolean greater(int[] part1, int p1, int[] part2, int p2){
while (p1<part1.length && p2<part2.length && part1[p1]==part2[p2]){
p1++;
p2++;
}

return p2==part2.length || (p1 < part1.length && part1[p1] > part2[p2]);
}
}
```

## Problem solution in C++.

```class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> result (k, 0);
vector<vector<int>> maxNumbers1=maxNumbers(nums1, min(k,(int)nums1.size()));
vector<vector<int>> maxNumbers2=maxNumbers(nums2, min((int)nums2.size(), k));

for (int i=0; i<=min(k, (int)nums1.size()); i++){
if (k-i<=min(k,(int)nums2.size())) {
vector<int> tem=merge(maxNumbers1[(int)maxNumbers1.size()-i-1], maxNumbers2[(int)maxNumbers2.size()-k+i-1]);
if (less_than(result, tem))
result=tem;
}
}

return result;
}

bool less_than(vector<int>& Number1, vector<int>& Number2){
int i=0;
while (i<Number1.size()){
if (Number1[i]<Number2[i]) return true;
else if (Number1[i]>Number2[i]) return false;
else i++;
}
return false;
}

vector<int> merge(vector<int>& Number1, vector<int>& Number2){
if (Number1.size()==0) return Number2;
if (Number2.size()==0) return Number1;
vector<int> result;
int i1=0, i2=0;
while (i1<Number1.size() || i2<Number2.size()){
if (i2==Number2.size()) {
result.push_back(Number1[i1]);
i1++;
}else if (i1==Number1.size()){
result.push_back(Number2[i2]);
i2++;
}
else if (Number1[i1]<Number2[i2]){
result.push_back(Number2[i2]);
i2++;
}else if (Number1[i1]>Number2[i2]){
result.push_back(Number1[i1]);
i1++;
}else {
int k1=i1, k2=i2;
while (k1<Number1.size() && k2<Number2.size() && Number1[k1]==Number2[k2]) {k1++; k2++;}
if (k1==Number1.size() || (k2<Number2.size() && Number2[k2]>Number1[k1])) {
result.push_back(Number2[i2]);
i2++;
}else {
result.push_back(Number1[i1]);
i1++;
}
}
}
return result;
}

vector<vector<int>> maxNumbers(vector<int>& nums1, int k){
vector<vector<int>> result;
vector<int> Number (nums1.begin(), nums1.begin()+k);
for (int i=k; i<nums1.size(); i++){
int j=0;
while (j+1<k && Number[j]>=Number[j+1]) j++;
if (j==k-1){
if (nums1[i]>Number[j]) Number[j]=nums1[i];
}
else {
Number.erase(Number.begin()+j);
Number.push_back(nums1[i]);
}
}
result.push_back(Number);
for (int i=0; i<k; i++){
int j=0;
while (j+1<Number.size() && Number[j]>=Number[j+1]) j++;
Number.erase(Number.begin()+j);
result.push_back(Number);
}

return result;
}

};
```

## Problem solution in C.

```void getMaxNumber(int *nums, int size, int outsize, int *out) {
int len = 0, i, k = size - outsize;
out[0] = nums[0];
for (i = 1; i < size; i++) {
while (len >= 0 && k > 0 && nums[i] > out[len]) k--, len--;
out[++len] = nums[i];
}
}

int compareArr(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int i;
for (i = 0; i < nums1Size && i < nums2Size && nums1[i] == nums2[i]; i++);
//if (i == nums1Size && i == nums2Size) return 0;
if (i == nums1Size) return -1;
if (i == nums2Size) return 1;
return (nums1[i] - nums2[i]);
}

void merge(int* nums1, int nums1Size, int* nums2, int nums2Size, int *out) {
int len = 0, i = 0, j = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] > nums2[j]) out[len++] = nums1[i++];
else if (nums1[i] < nums2[j]) out[len++] = nums2[j++];
else if (compareArr(nums1 + i, nums1Size - i, nums2 + j, nums2Size - j) >= 0) out[len++] = nums1[i++];
else out[len++] = nums2[j++];
}
while (i < nums1Size) out[len++] = nums1[i++];
while (j < nums2Size) out[len++] = nums2[j++];
}

int compare(int *arr1, int *arr2, int len) {
int i = 0;
for (; i < len && arr1[i] == arr2[i]; i++);
if (i < len) return arr1[i] - arr2[i];
return 0;
}

int min(int x, int y) {return x <= y ? x: y;}

int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) {
int i = 0, j = 0;
int *arr1, *arr2, *ans, *tmp;
if (k <= 0) {
*returnSize = 0;
return NULL;
}
arr1 = malloc(sizeof(int) * (nums1Size + nums2Size));
arr2 = arr1 + nums1Size;
ans = malloc(sizeof(int) * k);
tmp = malloc(sizeof(int) * k);
for (j = 0; j < k; j++) ans[j] = 0;
for (i = min(k, nums1Size); i >= 0; i--) {
j = k - i;
if (j > nums2Size) break;
if (i > 0) getMaxNumber(nums1, nums1Size, i, arr1);
if (j > 0) getMaxNumber(nums2, nums2Size, j, arr2);
merge(arr1, i, arr2, j, tmp);
if (compare(tmp, ans, k) > 0) {
for (j = 0; j < k; j++) ans[j] = tmp[j];
}
}
free(tmp);
free(arr1);
*returnSize = k;
return ans;
}
```