321. Create Maximum Number
Problem Description
You are tasked with creating the largest possible number by selecting k
digits from two given integer arrays nums1
and nums2
, where nums1
has a length m
and nums2
has a length n
. The number that you form must have the digits in the same relative order as they appear in their original arrays. The value k
satisfies the condition k <= m + n
, meaning the number of digits you select cannot be more than the total number of digits in both arrays combined.
Intuition
To solve this problem, we must break it down into smaller, manageable steps:
-
The core idea is to find the maximum number from each array by selecting
x
digits fromnums1
andk-x
digits fromnums2
, wherex
ranges frommax(0, k - n)
tomin(k, m)
. This implies thatx
needs to be in the range where it's valid for both arrays, considering their lengths. -
To get the maximum possible digits from a single array, we use a greedy approach with a stack. The function
f(nums, k)
in the solution uses a stack to build the maximum number of lengthk
from an arraynums
. It goes through the digits ofnums
and ensures that:- If the current digit is greater than the top of the stack and we still have more digits than we need (
remain > 0
), we pop from the stack. - We maintain a
remain
counter which allows us to discard digits we do not need, aiming to have exactlyk
digits in the stack. - We keep the stack filled up to
k
by pushing the current digit into it if not full.
- If the current digit is greater than the top of the stack and we still have more digits than we need (
-
Once we have the maximum digits from both arrays, we merge them into the largest possible number using the
merge(nums1, nums2)
function. This merge part maintains the relative order of the digits from both arrays. -
The merging is done by comparing the digits available to be merged: we take one digit at a time and pick the larger of the two unless they are equal. If they are equal, we look ahead and choose the digit from the number that has a larger following digit (
compare(nums1, nums2, i, j)
). This effectively ensures we are always picking the larger number that can be formed. -
To get the final answer, we iterate over all valid
x
and merge the respective maximum numbers possible, then compare them to find the best (maximum) combination of digits to form the actual largest number.
The given solution combines all these elements into a comprehensive algorithm to solve the problem. It finely balances between a greedy approach and careful selection to construct the largest number while adhering to the constraints imposed by the order of digits in the given arrays.
Learn more about Stack, Greedy and Monotonic Stack patterns.
Solution Approach
The solution uses a combination of greedy strategy and dynamic programming to approach this problem. Several key algorithms and patterns are applied in the solution code:
-
Greedy stack-based approach for subarray maximum: The
f(nums, k)
function implements a greedy strategy with a stack to selectk
digits from a given arraynums
while preserving their order to form the maximum possible number. It uses a stack (stk
) where each insertion is done using the following logic:- While the stack is not empty, the top of the stack is less than the current element (
stk[top] < x
), and there are more elements remaining to consider (remain > 0
), the top element is removed. This ensures only the largest elements are retained in the final selection. - An element is pushed to the stack if there is room (
top + 1 < k
), which represents potential digits for our final answer. - The
remain
count is a balance to maintain the proper number of digits. It's reduced whenever an element is not used.
- While the stack is not empty, the top of the stack is less than the current element (
-
Comparison function for lexicographical order: The
compare(nums1, nums2, i, j)
function determines which of two sequences will lead to a larger number if we start merging from them. The function is based on lexicographical comparison: it starts comparing digit by digit and keeps on going until it finds a larger digit or reaches the end of one array. This is a essential for properly merging two arrays to form the largest number. -
Merging two sequences preserving order: The
merge(nums1, nums2)
function is used to merge two sequences into the largest possible number while preserving the original relative order of digits withinnums1
andnums2
. This function usescompare
to choose the larger value at each step of the merge. -
Dynamic programming to test different combinations: The solution iterates over all valid values of
x
, wherex
is the number of digits taken fromnums1
andk-x
fromnums2
. By using the functionsf(nums1, x)
andf(nums2, k-x)
for generating the two maximum numbers (withx
andk-x
digits respectively) and then using themerge
function, the code tests all possible combinations to create the largest number of lengthk
. -
Use of a simple for loop to find the best combination: A for loop ranging from
l
tor
(for x in range(l, r + 1)
) serves to generate all validarr1
andarr2
combinations and then merges them. The loop constructs and compares the different combinations to keep track of the overall maximum (ans
).
The solution uses immensely crucial data structures, like the stack, which greatly simplifies adding and removing elements while maintaining the maximum digit ordering. It also heavily relies on the recursion (in compare
) to handle the comparison of the two sequences, and structural iteration to check each possible combination for the most optimal result.
Each function is dedicated to a specific part of the problem, modularizing the code and making the overall approach quite robust and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example. Consider the two integer arrays nums1 = [3, 4, 6]
and nums2 = [9, 1, 2]
, and let k = 5
(we want to create the largest possible number by selecting k
digits from nums1
and nums2
).
1. Greedy stack-based approach for subarray maximum
-
For
x = 2
(selecting 2 digits fromnums1
): Applyf(nums1, 2)
resulting in[4, 6]
. Here's how:- Start with an empty stack and
nums1[0] = 3
.remain
will be 1 (k-x=3
). Push3
to the stack. - Next,
nums1[1] = 4
. Since4 > 3
(top of the stack), pop3
and push4
. - Finally,
nums1[2] = 6
which is greater than the top again, so push6
. - The stack now has
[4, 6]
.
- Start with an empty stack and
-
For
k-x = 3
(selecting 3 digits fromnums2
): Applyf(nums2, 3)
and get[9, 2]
. The process is similar to the above.- Since
f(nums2, 3)
would initially pick[9, 1, 2]
, but1
would be popped out for2
considering the same logic expressed above.
- Since
2. Merging two sequences preserving order
- Merge
[4, 6]
and[9, 2]
by selecting the highest digit available from the front of each array while maintaining relative order usingmerge
.- First, compare
4
and9
, choose9
. - Then, compare
4
and2
, choose4
. - Next,
6
is the only digit left innums1
so choose6
. - Finally,
2
is the only digit left fromnums2
so choose2
. - The merged array is
[9, 4, 6, 2]
.
- First, compare
3. Use of a for loop to find the best combination
- Repeat steps 1 and 2 for all valid values of
x
(0 to 3 in this case) and keep track of the largest result (ans
).- If
x = 0
, this means all digits are selected fromnums2
: Merge[]
and[9, 1, 2]
to get[9, 1, 2]
. - If
x = 1
, select 1 fromnums1
and 4 fromnums2
. Merge[6]
and[9, 2]
to get[9, 6, 2]
. - If
x = 3
, all digits are selected fromnums1
: Merge[3, 4, 6]
and[]
to get[3, 4, 6]
.
- If
Final Result
Compare all the results and select the largest one:
[9, 1, 2]
is not the largest since we can have a larger digit in front by selecting fromnums1
.[9, 6, 2]
is larger than[9, 1, 2]
.[9, 4, 6, 2]
is the largest since it starts with9
and is followed by larger digits as compared with the alternatives.
So the largest number that can be created by selecting k = 5
digits from nums1
and nums2
is [9, 4, 6, 2]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
5 # Function to find the maximum number formed by k digits from the given list
6 def find_max_sequence(nums: List[int], k: int) -> List[int]:
7 stack = [0] * k # Initialize a stack to store the max number sequence
8 to_remove = len(nums) - k # Calculate how many digits we can remove
9 top = -1
10
11 for num in nums:
12 while top >= 0 and stack[top] < num and to_remove > 0:
13 top -= 1 # Pop from stack
14 to_remove -= 1
15 if top + 1 < k: # If there is space in stack, push the current number
16 top += 1
17 stack[top] = num
18 else:
19 to_remove -= 1
20
21 return stack
22
23 # Compare two sequences to determine which one is greater
24 def is_greater(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
25 while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
26 i += 1
27 j += 1
28 return j == len(nums2) or (i < len(nums1) and nums1[i] > nums2[j])
29
30 # Merge two sequences into the largest possible number
31 def merge(nums1: List[int], nums2: List[int]) -> List[int]:
32 merged = []
33 i = j = 0
34 while i < len(nums1) or j < len(nums2):
35 if is_greater(nums1, nums2, i, j):
36 merged.append(nums1[i])
37 i += 1
38 else:
39 merged.append(nums2[j])
40 j += 1
41 return merged
42
43 # Iterate through all possible splits of k between nums1 and nums2
44 best_sequence = [0] * k
45 for count in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
46 candidate1 = find_max_sequence(nums1, count)
47 candidate2 = find_max_sequence(nums2, k - count)
48 candidate_merged = merge(candidate1, candidate2)
49 if best_sequence < candidate_merged:
50 best_sequence = candidate_merged
51
52 return best_sequence
53
1class Solution {
2 // Main function to calculate maximum number by combining two arrays with length k
3 public int[] maxNumber(int[] nums1, int[] nums2, int k) {
4 int m = nums1.length, n = nums2.length;
5 int leftBound = Math.max(0, k - n), rightBound = Math.min(k, m);
6 int[] result = new int[k];
7
8 // Iterate from the leftBound to the rightBound to find all possible combinations
9 for (int i = leftBound; i <= rightBound; ++i) {
10 int[] subsequence1 = getMaxSubsequence(nums1, i);
11 int[] subsequence2 = getMaxSubsequence(nums2, k - i);
12 int[] mergedArray = merge(subsequence1, subsequence2);
13
14 // Check if the current merged array is greater than the result we have
15 if (compare(mergedArray, result, 0, 0)) {
16 result = mergedArray;
17 }
18 }
19 return result;
20 }
21
22 // Helper function to get the maximum subsequence of length k from nums array
23 private int[] getMaxSubsequence(int[] nums, int k) {
24 int n = nums.length;
25 int[] stack = new int[k];
26 int top = -1;
27 int remaining = n - k;
28 for (int num : nums) {
29 // If the current element nums is greater than the last element of stack
30 // and we have more remaining elements to dispose, pop from stack
31 while (top >= 0 && stack[top] < num && remaining > 0) {
32 --top;
33 --remaining;
34 }
35 // Push the current element nums to stack if it's not full
36 if (top + 1 < k) {
37 stack[++top] = num;
38 } else {
39 --remaining;
40 }
41 }
42 return stack;
43 }
44
45 // Merge the two subsequences to a single array in lexicographically maximum order
46 private int[] merge(int[] nums1, int[] nums2) {
47 int m = nums1.length, n = nums2.length;
48 int[] result = new int[m + n];
49 int i = 0, j = 0;
50
51 // Merge the two arrays by selecting the larger current head element every time
52 for (int k = 0; k < m + n; ++k) {
53 if (compare(nums1, nums2, i, j)) {
54 result[k] = nums1[i++];
55 } else {
56 result[k] = nums2[j++];
57 }
58 }
59 return result;
60 }
61
62 // Compare two arrays from the given indices to find which array's number is greater
63 private boolean compare(int[] nums1, int[] nums2, int i, int j) {
64 int m = nums1.length, n = nums2.length;
65 // If we have reached the end of nums1, return false
66 if (i >= m) return false;
67 // If we have reached the end of nums2, return true
68 if (j >= n) return true;
69 // Compare the values at the current indices
70 if (nums1[i] > nums2[j]) return true;
71 if (nums1[i] < nums2[j]) return false;
72 // If values are the same, recursively compare the next indices
73 return compare(nums1, nums2, i + 1, j + 1);
74 }
75}
76
1#include <vector>
2#include <algorithm>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9 // Create the maximum number from a single vector by choosing exactly k elements.
10 vector<int> getMaxNumberFromSingleVector(vector<int>& nums, int k) {
11 int n = nums.size();
12 vector<int> stack(k);
13 int top = -1;
14 int remain = n - k;
15 for (int x : nums) {
16 // If the current element is greater than the top element of stack
17 // and we still have elements to remove, then pop the stack.
18 while (top >= 0 && stack[top] < x && remain > 0) {
19 --top;
20 --remain;
21 }
22 // Push to the stack if it's not full.
23 if (top + 1 < k) {
24 stack[++top] = x;
25 } else {
26 // Decrease the count of remaining elements we can skip.
27 --remain;
28 }
29 }
30 return stack;
31 }
32
33 // Compare two vectors to decide which vector can provide larger number in lexical order.
34 bool compareVectors(vector<int>& nums1, vector<int>& nums2, int i, int j) {
35 if (i >= nums1.size()) {
36 return false;
37 }
38 if (j >= nums2.size()) {
39 return true;
40 }
41 if (nums1[i] > nums2[j]) {
42 return true;
43 }
44 if (nums1[i] < nums2[j]) {
45 return false;
46 }
47 // If both numbers are equal, compare the next pair of elements.
48 return compareVectors(nums1, nums2, i + 1, j + 1);
49 }
50
51 // Merge two vectors into one in a way that forms the largest number
52 // by lexical order.
53 vector<int> mergeVectors(vector<int>& nums1, vector<int>& nums2) {
54 int m = nums1.size(), n = nums2.size();
55 int i = 0, j = 0;
56 vector<int> result(m + n);
57 for (int k = 0; k < m + n; ++k) {
58 // Choose the larger element from nums1 or nums2 to add to the result.
59 if (compareVectors(nums1, nums2, i, j)) {
60 result[k] = nums1[i++];
61 } else {
62 result[k] = nums2[j++];
63 }
64 }
65 return result;
66 }
67
68 // Main method to merge and find the maximum number formed by nums1 and nums2 of length k.
69 vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
70 int m = nums1.size(), n = nums2.size();
71 int start = max(0, k - n), end = min(k, m);
72 vector<int> ans(k, 0);
73 for (int x = start; x <= end; ++x) {
74 vector<int> subNums1 = getMaxNumberFromSingleVector(nums1, x);
75 vector<int> subNums2 = getMaxNumberFromSingleVector(nums2, k - x);
76 vector<int> merged = mergeVectors(subNums1, subNums2);
77 // Update the ans to the largest number.
78 if (ans < merged) {
79 ans = std::move(merged);
80 }
81 }
82 return ans;
83 }
84};
85
1function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
2 const nums1Length = nums1.length;
3 const nums2Length = nums2.length;
4 const leftBound = Math.max(0, k - nums2Length);