Create Maximum Number
Create Maximum Number is a hard monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (monotonic stack + greedy merge), runs in O(k · (m + n + k²)) time and O(m + n + k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (window scans for each split) up.
Problem
You are given two arrays of single digits, nums1 of length m and nums2 of length n, each standing for the digits of a number. You are also given an integer k with k <= m + n.
Build the largest possible number of exactly k digits using digits from both arrays. Digits taken from the same array must keep their original relative order, but digits from the two arrays can be interleaved freely.
Return the result as an array of its k digits.
Examples
Example 1
- Input
nums1 = [4, 9, 1], nums2 = [7, 2, 8], k = 4- Output
[9, 7, 8, 1]- Why
- Take 9, 1 from nums1 and 7, 8 from nums2 and interleave them. Taking only 9 from nums1 would force 7, 2, 8 and give the smaller 9, 7, 2, 8.
Example 2
- Input
nums1 = [3, 8], nums2 = [3, 1, 5], k = 5- Output
[3, 8, 3, 1, 5]- Why
- Every digit is used. Both arrays start with 3; taking nums1's 3 first lets its 8 come next, which beats 3, 3, 8, 1, 5.
Example 3
- Input
nums1 = [2, 0], nums2 = [1], k = 3- Output
[2, 1, 0]- Why
- All digits must be used; interleaving them as 2, 1, 0 beats 2, 0, 1 and 1, 2, 0.
Constraints
m == nums1.length,n == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + n
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (window scans for each split) | O(k · (m + n) · k) | O(k) |
| Optimal (monotonic stack + greedy merge) | O(k · (m + n + k²)) | O(m + n + k) |
1Brute force (window scans for each split)
O(k · (m + n) · k)For each of up to k + 1 splits, each picked digit scans up to m or n values, and the merge costs up to k² in the worst case.O(k)The two picked sequences and the merged candidate.For every split (i digits from nums1, k - i from nums2), build the largest subsequence of each array by picking digits one at a time: the next digit is the largest value in the window that still leaves enough digits after it. Merge the two picks greedily and keep the best result.
- For i from max(0, k - n) to min(k, m): a = pick(nums1, i), b = pick(nums2, k - i).
- pick(arr, t): for each of the t positions, scan arr[start .. len - remaining] for the first maximum, take it and continue after it.
- Merge a and b: repeatedly take from the sequence whose remaining suffix is larger.
- Keep the lexicographically largest merged array.
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length, n = nums2.length;
int[] best = new int[k];
for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
int[] cand = merge(pick(nums1, i), pick(nums2, k - i));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
}
private int[] pick(int[] arr, int t) {
int[] res = new int[t];
int start = 0;
for (int p = 0; p < t; p++) {
int last = arr.length - (t - p);
int bestIdx = start;
for (int j = start; j <= last; j++) {
if (arr[j] > arr[bestIdx]) bestIdx = j;
}
res[p] = arr[bestIdx];
start = bestIdx + 1;
}
return res;
}
private int[] merge(int[] a, int[] b) {
int[] res = new int[a.length + b.length];
int i = 0, j = 0;
for (int p = 0; p < res.length; p++) {
res[p] = greater(a, i, b, j) ? a[i++] : b[j++];
}
return res;
}
private boolean greater(int[] a, int i, int[] b, int j) {
while (i < a.length && j < b.length && a[i] == b[j]) {
i++;
j++;
}
return j == b.length || (i < a.length && a[i] > b[j]);
}
}class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
def pick(arr: List[int], t: int) -> List[int]:
res = []
start = 0
for p in range(t):
last = len(arr) - (t - p)
best_idx = start
for j in range(start, last + 1):
if arr[j] > arr[best_idx]:
best_idx = j
res.append(arr[best_idx])
start = best_idx + 1
return res
def merge(a: List[int], b: List[int]) -> List[int]:
res = []
i = j = 0
while i < len(a) or j < len(b):
if a[i:] > b[j:]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
return res
m, n = len(nums1), len(nums2)
best = [0] * k
for i in range(max(0, k - n), min(k, m) + 1):
cand = merge(pick(nums1, i), pick(nums2, k - i))
if cand > best:
best = cand
return bestclass Solution {
vector<int> pick(const vector<int>& arr, int t) {
vector<int> res;
int start = 0;
for (int p = 0; p < t; p++) {
int last = arr.size() - (t - p);
int bestIdx = start;
for (int j = start; j <= last; j++) {
if (arr[j] > arr[bestIdx]) bestIdx = j;
}
res.push_back(arr[bestIdx]);
start = bestIdx + 1;
}
return res;
}
bool greater(const vector<int>& a, int i, const vector<int>& b, int j) {
while (i < (int)a.size() && j < (int)b.size() && a[i] == b[j]) {
i++;
j++;
}
return j == (int)b.size() || (i < (int)a.size() && a[i] > b[j]);
}
vector<int> merge(const vector<int>& a, const vector<int>& b) {
vector<int> res;
int i = 0, j = 0;
while (i < (int)a.size() || j < (int)b.size()) {
if (greater(a, i, b, j)) res.push_back(a[i++]);
else res.push_back(b[j++]);
}
return res;
}
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
vector<int> best(k, 0);
for (int i = max(0, k - n); i <= min(k, m); i++) {
vector<int> cand = merge(pick(nums1, i), pick(nums2, k - i));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
}
};function maxNumber(nums1, nums2, k) {
function pick(arr, t) {
const res = [];
let start = 0;
for (let p = 0; p < t; p++) {
const last = arr.length - (t - p);
let bestIdx = start;
for (let j = start; j <= last; j++) {
if (arr[j] > arr[bestIdx]) bestIdx = j;
}
res.push(arr[bestIdx]);
start = bestIdx + 1;
}
return res;
}
function greater(a, i, b, j) {
while (i < a.length && j < b.length && a[i] === b[j]) {
i++;
j++;
}
return j === b.length || (i < a.length && a[i] > b[j]);
}
function merge(a, b) {
const res = [];
let i = 0, j = 0;
while (i < a.length || j < b.length) {
if (greater(a, i, b, j)) res.push(a[i++]);
else res.push(b[j++]);
}
return res;
}
const m = nums1.length, n = nums2.length;
let best = new Array(k).fill(0);
for (let i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
const cand = merge(pick(nums1, i), pick(nums2, k - i));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
}2Optimal (monotonic stack + greedy merge)
O(k · (m + n + k²))Each split costs O(m + n) to build both subsequences and at most O(k²) to merge (ties are usually short, so it is close to O(k) in practice).O(m + n + k)The stacks and the merged candidate.Same split-and-merge plan, but each best subsequence is built in one pass with a decreasing stack: while the incoming digit is larger than the top and there are still digits we are allowed to drop (len - t in total), pop the top. Push the digit if the stack holds fewer than t digits. The merge is unchanged: on a tie, the sequence with the larger remaining suffix goes first.
- For i from max(0, k - n) to min(k, m): a = maxSubsequence(nums1, i), b = maxSubsequence(nums2, k - i).
- maxSubsequence(arr, t): drop = arr.length - t; for each digit, pop while drop > 0 and the top is smaller (drop--), then push if the stack has fewer than t digits.
- Merge a and b by comparing suffixes, and keep the largest merged array.
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length, n = nums2.length;
int[] best = new int[k];
for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
int[] cand = merge(maxSubsequence(nums1, i), maxSubsequence(nums2, k - i));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
}
private int[] maxSubsequence(int[] arr, int t) {
int[] stack = new int[t];
int top = 0;
int drop = arr.length - t;
for (int x : arr) {
while (top > 0 && drop > 0 && stack[top - 1] < x) {
top--;
drop--;
}
if (top < t) stack[top++] = x;
else drop--;
}
return stack;
}
private int[] merge(int[] a, int[] b) {
int[] res = new int[a.length + b.length];
int i = 0, j = 0;
for (int p = 0; p < res.length; p++) {
res[p] = greater(a, i, b, j) ? a[i++] : b[j++];
}
return res;
}
private boolean greater(int[] a, int i, int[] b, int j) {
while (i < a.length && j < b.length && a[i] == b[j]) {
i++;
j++;
}
return j == b.length || (i < a.length && a[i] > b[j]);
}
}class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
def max_subsequence(arr: List[int], t: int) -> List[int]:
stack = []
drop = len(arr) - t
for x in arr:
while stack and drop > 0 and stack[-1] < x:
stack.pop()
drop -= 1
if len(stack) < t:
stack.append(x)
else:
drop -= 1
return stack
def merge(a: List[int], b: List[int]) -> List[int]:
res = []
i = j = 0
while i < len(a) or j < len(b):
if a[i:] > b[j:]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
return res
m, n = len(nums1), len(nums2)
best = [0] * k
for i in range(max(0, k - n), min(k, m) + 1):
cand = merge(max_subsequence(nums1, i), max_subsequence(nums2, k - i))
if cand > best:
best = cand
return bestclass Solution {
vector<int> maxSubsequence(const vector<int>& arr, int t) {
vector<int> stack;
int drop = arr.size() - t;
for (int x : arr) {
while (!stack.empty() && drop > 0 && stack.back() < x) {
stack.pop_back();
drop--;
}
if ((int)stack.size() < t) stack.push_back(x);
else drop--;
}
return stack;
}
bool greater(const vector<int>& a, int i, const vector<int>& b, int j) {
while (i < (int)a.size() && j < (int)b.size() && a[i] == b[j]) {
i++;
j++;
}
return j == (int)b.size() || (i < (int)a.size() && a[i] > b[j]);
}
vector<int> merge(const vector<int>& a, const vector<int>& b) {
vector<int> res;
int i = 0, j = 0;
while (i < (int)a.size() || j < (int)b.size()) {
if (greater(a, i, b, j)) res.push_back(a[i++]);
else res.push_back(b[j++]);
}
return res;
}
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
vector<int> best(k, 0);
for (int i = max(0, k - n); i <= min(k, m); i++) {
vector<int> cand = merge(maxSubsequence(nums1, i), maxSubsequence(nums2, k - i));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
}
};function maxNumber(nums1, nums2, k) {
function maxSubsequence(arr, t) {
const stack = [];
let drop = arr.length - t;
for (const x of arr) {
while (stack.length > 0 && drop > 0 && stack[stack.length - 1] < x) {
stack.pop();
drop--;
}
if (stack.length < t) stack.push(x);
else drop--;
}
return stack;
}
function greater(a, i, b, j) {
while (i < a.length && j < b.length && a[i] === b[j]) {
i++;
j++;
}
return j === b.length || (i < a.length && a[i] > b[j]);
}
function merge(a, b) {
const res = [];
let i = 0, j = 0;
while (i < a.length || j < b.length) {
if (greater(a, i, b, j)) res.push(a[i++]);
else res.push(b[j++]);
}
return res;
}
const m = nums1.length, n = nums2.length;
let best = new Array(k).fill(0);
for (let i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
const cand = merge(maxSubsequence(nums1, i), maxSubsequence(nums2, k - i));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
}Edge cases to test
- k equals m + n: every digit is used and only the merge order matters
- All digits taken from one array
- Equal digits at the front of both sequences during the merge: look further ahead to break the tie
- Many zeros and repeated digits
Hints
Hint 1
Fix how many digits i come from nums1; the other k - i come from nums2. Try every valid i.
Hint 2
For a fixed count, the best subsequence of one array is found greedily with a monotonic stack (drop a smaller top while you can still afford to drop digits).
Hint 3
Merging two sequences is like merge sort, but on a tie compare the remaining suffixes and take from the larger one.
FAQ
What is the best time complexity for Create Maximum Number?
Optimal (monotonic stack + greedy merge) runs in O(k · (m + n + k²)) time and O(m + n + k) extra space. Each split costs O(m + n) to build both subsequences and at most O(k²) to merge (ties are usually short, so it is close to O(k) in practice).
Which pattern does Create Maximum Number use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Create Maximum Number?
Yes. Brute force (window scans for each split) takes O(k · (m + n) · k) time and O(k) space. For every split (i digits from nums1, k - i from nums2), build the largest subsequence of each array by picking digits one at a time: the next digit is the largest value in the window that still leaves enough digits after it.
Which edge cases should I test for Create Maximum Number?
k equals m + n: every digit is used and only the merge order matters; All digits taken from one array; Equal digits at the front of both sequences during the merge: look further ahead to break the tie; Many zeros and repeated digits.