Problem: Given two arrays which only contains digits 0 - 9 of lengths say m and n represents two numbers. Create the maximum number of length k <= m + n from digits of the input two arrays. The relative order of the digits from the same array must be preserved. Return an array of the k digits.
Example:
Input:
nums1 = [6, 0, 1, 2]
nums2 = [6, 7, 3]
k = 5
Output:
[7, 6, 3, 1, 2]
Approach: Let's breakdown this problem into sub problems:
1. Given an array of length n, create the maximum number of length k. Basically instead of looking at 2 arrays, just look at one array:
This is straight forward, we can do it using the stack. Here is the algorithm:
- stack = empty stack
- FOREACH i from 0 to n:
- WHILE stack is not empty AND top of stack < array[i] AND n - i + number of elements in stack > k
- IF number of elements in stack < k
- Add all the elements of the stack in an array in reverse order and return this array
Let me explain what exactly "WHILE stack is not empty AND top of stack < array[i] AND n - i + number of elements in stack > k" condition is checking; basically its saying pop the top of stack if it is smaller than array[i] until either stack is empty or the number of digits left in the array is not enough to fill the stack to size k.
2. Given two array say array1 and array2 of length m and n, create maximum number of length k = m + n: This problem is lot closer to the original problem with the exception that we will use all the digits we have.
Let's say result is the array of size k which we want to return. We can use the approach similar to merge method of merge sort where we just fill the greater digit in result by comparing current element of array1 and current element of array2 and increment the index of the array from where we find the larger digit. This looks good and works until we find current digits of both the arrays are same. Which one we should choose here? In case of merge sort, it does not matter which one we choose but here it does matter. Let's see it by example. Say we have following 2 arrays:
- [6, 0]
- [6, 7]
Now in this case when current digit of both array is 6, we just can't take any 6, we need to take 6 from array 2 as then we will get the maximum number which is [6, 7, 6, 0] otherwise if we took the 6 from array 1 the number which we have gotten is [6, 6, 7, 0] which is clearly not the maximum number. That means in case of same digits we need to look further into both strings until we get different digits and choose the array where we get the greater digit. So you see our merge algorithm will be almost same as merge method of merge sort except here we will use a method say IsGreater (which will look further in both strings until we get the different digits) instead of usual greater than '>' operator. Here is the algorithm for merge method:
- result = []
- i = 0, j = 0
- FOR resultIndex = 0 To k
- IF IsGreater(array1, i, array2, j)
- result[resultIndex] = array1[i]
- i = i + 1
- ELSE
- result[resultIndex] = array2[j]
- j = j + 1
- return result
Now here is the algorithm for IsGreater method:
- WHILE array1[i] == array2[j] // Looking further till we get same digits
- return array1[i] > array2[i]
Of course we need to handle some boundary conditions which you can see in the implementation in the above algorithm. I did not put it here just to make core logic simple to understand.
Now given we have solved above subproblems we can go back to our original problem which will be fairly easy to solve using the solution of above subproblems:
- First, we divide the k digits required into two parts; i and k-i.
- Find the maximum number of length i in one array and the maximum number of length k-i in the other array using the algorithm of subproblem 1.
- Merge the two results of step 2 in to one array using the algorithm of subproblem 2.
- Compare the current result with final result and assign the current result to final result if current result is greater than final result. We can use IsGreater method of subproblem 2 to identify which one is greater.
That's all!
Implementation in C#:
public static int[] MaxNumberOfTwoArray(int[] nums1, int[] nums2, int k)
{
if ( k > nums1?.Length + nums2?.Length)
{
return null;
}
int[] maxNumber = new int[k];
// Dividing k into i and k -i
for (int i = Math.Max(0, k - nums2.Length); i <= k && i <= nums1.Length; ++i)
{
int[] currNumber = MergeMaxNumbers(MaxNumberOfOneArray(nums1, i), MaxNumberOfOneArray(nums2, k - i), k);
if (IsGreater(currNumber, 0, maxNumber, 0))
{
maxNumber = currNumber;
}
}
return maxNumber;
}
private static int[] MaxNumberOfOneArray(int[] nums, int k)
{
Stack<int> stack = new Stack<int>();
for (int i = 0; i < nums.Length; ++i)
{
while (stack.Count > 0 && nums.Length - i + stack.Count > k && stack.Peek() < nums[i])
{
stack.Pop();
}
if (stack.Count < k)
{
stack.Push(nums[i]);
}
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; --i)
{
result[i] = stack.Pop();
}
return result;
}
private static int[] MergeMaxNumbers(int[] nums1, int[] nums2, int k)
{
int[] result = new int[k];
for (int nums1I = 0, nums2I = 0, resultI = 0; resultI < k; ++resultI)
{
result[resultI] = IsGreater(nums1, nums1I, nums2, nums2I) ? nums1[nums1I++] : nums2[nums2I++];
}
return result;
}
private static bool IsGreater(int[] nums1, int nums1I, int[] nums2, int nums2I)
{
while (nums1I < nums1.Length && nums2I < nums2.Length && nums1[nums1I] == nums2[nums2I])
{
++nums1I;
++nums2I;
}
return nums2I == nums2.Length || (nums1I < nums1.Length && nums1[nums1I] > nums2[nums2I]);
}
Complexity: O(k * (m + n)) where m is the size of nums1 and n is the size of nums2
