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);
5 const rightBound = Math.min(k, nums1Length);
6 let maxSequence: number[] = Array(k).fill(0);
7
8 // Try all possible sizes combinations for sequences taken from nums1 and nums2
9 for (let sizeFromNums1 = leftBound; sizeFromNums1 <= rightBound; ++sizeFromNums1) {
10 const sequenceFromNums1 = getMaxSequence(nums1, sizeFromNums1);
11 const sequenceFromNums2 = getMaxSequence(nums2, k - sizeFromNums1);
12 const mergedSequence = mergeSequences(sequenceFromNums1, sequenceFromNums2);
13
14 // Update the result if the new sequence is greater
15 if (compareSequences(mergedSequence, maxSequence, 0, 0)) {
16 maxSequence = mergedSequence;
17 }
18 }
19 return maxSequence;
20}
21
22// Get the maximum sequence of given length k from nums
23function getMaxSequence(nums: number[], k: number): number[] {
24 const stack: number[] = Array(k).fill(0);
25 let top = -1;
26 let remaining = nums.length - k;
27
28 // Construct the maximum sequence
29 for (const num of nums) {
30 while (top >= 0 && stack[top] < num && remaining > 0) {
31 --top;
32 --remaining;
33 }
34 if (top + 1 < k) {
35 stack[++top] = num;
36 } else {
37 --remaining;
38 }
39 }
40 return stack;
41}
42
43// Compare two sequences to see if nums1 is greater than nums2 starting from indices i and j
44function compareSequences(nums1: number[], nums2: number[], i: number, j: number): boolean {
45 // If we reached the end of nums1, nums2 is greater or equal
46 if (i >= nums1.length) {
47 return false;
48 }
49 // If we reached the end of nums2, nums1 is greater
50 if (j >= nums2.length) {
51 return true;
52 }
53 // Direct comparison if elements are different
54 if (nums1[i] > nums2[j]) {
55 return true;
56 }
57 if (nums1[i] < nums2[j]) {
58 return false;
59 }
60 // If elements are the same, move to the next element
61 return compareSequences(nums1, nums2, i + 1, j + 1);
62}
63
64// Merge two sequences into the largest possible sequence
65function mergeSequences(nums1: number[], nums2: number[]): number[] {
66 const nums1Length = nums1.length;
67 const nums2Length = nums2.length;
68 const merged: number[] = Array(nums1Length + nums2Length).fill(0);
69 let index1 = 0;
70 let index2 = 0;
71
72 // Merge two sequences by choosing the greater element at each step
73 for (let k = 0; k < merged.length; ++k) {
74 if (compareSequences(nums1, nums2, index1, index2)) {
75 merged[k] = nums1[index1++];
76 } else {
77 merged[k] = nums2[index2++];
78 }
79 }
80 return merged;
81}
82
Time and Space Complexity
The given Python code defines a problem of combining two numbers (nums1
and nums2
) into the largest number possible of length k
, where only elements from the same array maintain their original order.
Time Complexity:
The overall time complexity of the algorithm can be broken down into three parts: finding the maximum sub-sequence of a certain length from one array, comparing two sequences to see which one is greater, and merging the two sequences into one.
-
Finding Maximum Sub-sequence (
f
function): For one array (say nums1 of lengthm
), finding a maximum sub-sequence of lengthx
requires a single pass through the original numbers, which takesO(m)
. This sub-sequence process needs to be done at mostmin(k, m) - max(0, k - n) + 1
times, wherek
is the required total length,m
is the length ofnums1
, andn
is the length ofnums2
. -
Comparing Two Sequences (
compare
function): This recursive comparison function has the feature of early termination when a different pair of numbers is encountered. In the worst case, it might need to go through the entire lengths of both nums1 and nums2, which arem
andn
respectively. So, the time complexity in the worst case would beO(m + n)
. However, this function tends to perform better than the worst case in practice. -
Merging Two Sequences (
merge
function): Merging two sequences of lengthsx
andk-x
involves looking at each of the k elements once, resulting in a time complexity ofO(k)
for every merge.
The combined time complexity of these processes, considering the loop that tries every valid combination of lengths x
from nums1
and k-x
from nums2
, is O((min(k, m) - max(0, k - n) + 1) * (m + n + k))
. Given the worst-case scenario where the difference between min(k, m)
and max(0, k - n)
is maximal, this results in O(k * (m + n + k))
.
Space Complexity:
The space complexity is primarily determined by the storage required for the stack in f
function, the merging operation, and internal stack usage for recursion in comparison (in the compare
function):
-
Stack in
f
function: A stack of sizek
is used, leading to a space complexity ofO(k)
for the stack. -
Merging Two Sequences: The
merge
function uses a temporary list to store the merged sequence, also of sizek
, contributingO(k)
to the space complexity. -
Comparing Two Sequences (Recursion Overhead): The recursion used in the
compare
function can potentially go as deep asm + n
, so in the worst case, there is an additional space complexity ofO(m + n)
due to recursion stack.
Therefore, considering these separate contributions, the overall space complexity of the algorithm is O(k + m + n)
. This accounts for the stack in the f
function, the merged array, and the potential system stack usage during the compare
recursive calls.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.