Create Maximum Number - Leetcode Solution

Problem statement:

Given two arrays of digits nums1 and nums2, return the maximum number you can create using both arrays. The maximum number should be sorted in non-increasing order.

Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3] Output: [9,8,6,5,3] Explanation: We have three possible largest numbers:

• [9,8,6,5,3]
• [9,8,6,5,2]
• [9,8,6,4,3] The largest number is [9,8,6,5,3].

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4] Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9] Output: [9,8,9,3]

Solution:

The problem can be solved using greedy approach. We need to find the maximum possible number for each of the arrays separately and then combine them to find the maximum possible number.

Let's define a function named "get_max" which takes an array of digits and a number k as input and returns the maximum possible number that can be created using k digits.

Algorithm:

1. Initialize an empty stack to store the result.
2. Traverse the array from left to right
   • while stack is not empty and top element is less than the current element and the size of stack plus remaining elements in array is greater than k then pop the stack
   • if stack size is less than k then push the current element in stack
3. If stack size is greater than k then pop elements from stack till the size becomes k
4. Convert the stack to a list and return it as the result.

Code:

def get_max(nums, k): stack = [] n = len(nums) for i in range(n): while stack and stack[-1] < nums[i] and len(stack) + n - i > k: stack.pop() if len(stack) < k: stack.append(nums[i]) return stack

Now, we can use the above function to find the maximum number that can be created using both arrays jointly.

Algorithm:

1. Initialize two pointers p1 and p2 to zero.
2. Traverse the arrays until p1 and p2 are within their bounds
   • if nums1[p1:] is larger than nums2[p2:] then append nums1[p1] to result, increment p1
   • else append nums2[p2] to result, increment p2
3. Append remaining elements in nums1[p1:] and nums2[p2:] to the result.
4. Find the maximum possible number by calling get_max function on the result array.

Code:

def merge(nums1, nums2): res = [] n, m = len(nums1), len(nums2) p1, p2 = 0, 0 while p1 < n and p2 < m: if nums1[p1:] > nums2[p2:]: res.append(nums1[p1]) p1 += 1 else: res.append(nums2[p2]) p2 += 1 res += nums1[p1:] + nums2[p2:] return res

def maxNumber(nums1, nums2, k): res = [] n, m = len(nums1), len(nums2) for i in range(max(0, k - m), min(k, n) + 1): temp = merge(get_max(nums1, i), get_max(nums2, k - i)) if temp > res: res = temp return res

The time complexity of this solution is O((m + n)^3 * log(m + n)) which is not very efficient for large inputs. However, this solution passes all test cases on leetcode.

1