Problem

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.

Examples

Example 1:

1
2

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

1
2

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

Example 3:

1
2

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

Constraints

  • m == nums1.length
  • n == nums2.length
  • 1 <= m, n <= 500
  • 0 <= nums1[i], nums2[i] <= 9
  • 1 <= k <= m + n

Solution

Method 1 - Break in 3 Subproblems

We need to formulate the maximum number of length k from digits of two arrays nums1 and nums2. This problem can be broken down into three subproblems:

  1. Extract the largest k numbers from an array while maintaining relative order.
  2. Merge two arrays to form the largest possible number.
  3. Compare two arrays for their values to decide on a lexicographically larger sequence.

Subproblem 1 - Get K Largest Numbers Keeping Relative Order in a Single Array

We can solve this subproblem using a greedy strategy with the help of a stack. The steps are:

  • Initialize an empty stack.
  • Traverse the array nums:
    • Pop elements from the stack if they are smaller than the current element until:
      1. The stack is empty.
      2. The remaining elements plus stack size are insufficient to fill k slots.
    • Push the current element onto the stack if its size is less than k.
  • Return the stack.

Since the stack length is known to be k, it is very easy to use an array to simulate the stack.

This ensures that each element is pushed and popped at most once, thus the time complexity is O(n).

Subproblem 2: Merge Two Arrays

Given two arrays nums1 and nums2 of lengths m and n. Now, this is close to the original problem with the difference that we will use all the digits. We create the maximum number of length k = m + n using a greedy approach:

  • We need k decisions to make, and each time we decide whether ans[i] is from nums1 or nums2.
  • Compare the subsequent digits when elements are equal; choose the larger number from further elements, if they aren’t equal.
  • If arrays are the same until their end, then pick either.

For e.g.

1
2
3
4

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
ans = [6, 7, 6, 0, 4]

We decide to choose the 6 from nums1 at step 1, because 7 > 0. What if they are equal again? We continue to look the next digit until they are not equal. If all digits are equal then choose any one is ok.

This resembles the merge step of the merge sort algorithm but checks further elements when they are equal, leading to a complexity of O(m * n), where m and n are the lengths of nums1 and nums2.

Final Solution

To solve the final problem:

  1. Iterate through each combination of lengths taken from nums1 and nums2 summing up to k.
  2. Use the subproblems to get the maximum subsequence and merge to form the result.
  3. Return the maximum result by comparing all possible combinations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class Solution {
    // Get the largest k numbers while keeping relative order
    private int[] maxNumberOfSingleArray(int[] nums, int k) {
        int[] ans = new int[k];
        if (k == 0) return ans;
        
        int n = nums.length;
        int idx = 0;
        
        for (int i = 0; i < n; i++) {
            while ((n - i - 1) + (idx + 1) > k && idx > 0 && nums[i] > ans[idx - 1]) {
                idx--;
            }
            if (idx < k) {
                ans[idx++] = nums[i];
            }
        }
        return ans;
    }
    
    // Compare two arrays at the "start" index
    private boolean compareTwoArrays(int[] nums1, int startIdx1, int[] nums2, int startIdx2) {
        int len1 = nums1.length - startIdx1;
        int len2 = nums2.length - startIdx2;
        int len = Math.max(len1, len2);
        
        for (int i = 0; i < len; i++) {
            int digit1 = startIdx1 + i < nums1.length ? nums1[startIdx1 + i] : 0;
            int digit2 = startIdx2 + i < nums2.length ? nums2[startIdx2 + i] : 0;
            if (digit1 != digit2) {
                return digit1 > digit2;
            }
        }
        return true;
    }

    // Merge two arrays to create maximum number
    private int[] mergeTwoArrays(int[] nums1, int[] nums2, int k) {
        int[] result = new int[k];
        int idx1 = 0, idx2 = 0;
        int idx = 0;
        
        while (idx < k) {
            if (compareTwoArrays(nums1, idx1, nums2, idx2)) {
                result[idx++] = nums1[idx1++];
            } else {
                result[idx++] = nums2[idx2++];
            }
        }
        return result;
    }

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] result = new int[k];
        
        if (len1 + len2 < k) {
            return result; // Invalid case
        }
        
        for (int i = 0; i <= k; i++) {
            if (i <= len1 && (k - i) <= len2) {
                int[] maxNumbers1 = maxNumberOfSingleArray(nums1, i);
                int[] maxNumbers2 = maxNumberOfSingleArray(nums2, k - i);
                int[] maxNumbers = mergeTwoArrays(maxNumbers1, maxNumbers2, k);
                if (compareTwoArrays(maxNumbers, 0, result, 0)) {
                    result = maxNumbers;
                }
            }
        }
        
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution:
    # Get the largest k numbers while keeping relative order
    def max_number_of_single_array(self, nums: List[int], k: int) -> List[int]:
        stack = []
        drop = len(nums) - k

        for num in nums:
            while drop and stack and stack[-1] < num:
                stack.pop()
                drop -= 1
            stack.append(num)
        return stack[:k]

    # Compare two arrays starting from the given indices
    def compare_two_arrays(self, nums1: List[int], idx1: int, nums2: List[int], idx2: int) -> bool:
        while idx1 < len(nums1) and idx2 < len(nums2) and nums1[idx1] == nums2[idx2]:
            idx1 += 1
            idx2 += 1
        return idx2 == len(nums2) or (idx1 < len(nums1) and nums1[idx1] > nums2[idx2])

    # Merge two arrays to create maximum number of length k
    def merge_two_arrays(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        ans = []
        while k:
            if self.compare_two_arrays(nums1, 0, nums2, 0):
                ans.append(nums1.pop(0))
            else:
                ans.append(nums2.pop(0))
            k -= 1
        return ans

    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        len1, len2 = len(nums1), len(nums2)
        result = []

        for i in range(max(0, k - len2), min(k, len1) + 1):
            candidate = self.merge_two_arrays(
                self.max_number_of_single_array(nums1, i),
                self.max_number_of_single_array(nums2, k - i),
                k
            )
            if candidate > result:
                result = candidate
        return result

Complexity

  • ⏰ Time complexity: O((m + n)^2), where m and n are the lengths of nums1 and nums2 due to multiple merges and comparisons.
  • 🧺 Space complexity: O(k), as we are using extra space for storing the results and intermediate arrays.