Create Maximum Number — Solution in Python, Java & C++
Create Maximum Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and greedy.
Create Maximum Number is a hard coding problem on arrays, greedy and stack, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Greedy, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two arrays nums1 and nums2 hold the digits of two numbers (each element is a digit 0–9). Pick exactly k digits in total from the two arrays and line them up into a new number. The digits taken from the same array must keep their original relative order; digits from the two arrays may be interleaved freely.
Return the largest number you can build, as an array of its k digits.
Example 1
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]
Example 2
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]
Explanation: All five digits are used; starting with `nums1`'s 6 lets the 7 come second.
Example 3
Input: nums1 = [2,8,1], nums2 = [7,3,9], k = 3
Output: [9,8,1]
Explanation: Take the 9 from `nums2` first, then 8 and 1 from `nums1`.
Constraints
m == nums1.lengthn == nums2.length1 <= m, n <= 5000 <= nums1[i], nums2[i] <= 91 <= k <= m + n
Hints for Create Maximum Number
Hint 1
Split the job: take
sdigits fromnums1andk - sfromnums2, for every feasibles.Hint 2
The best
tdigits of a single array, in order, come from a monotonic stack: pop a smaller top while you can still afford to drop digits.Hint 3
Merge the two picks like merge sort, but when the heads are equal compare the remaining suffixes to decide which array to take from. Keep the best merged result over all
s.
How to solve Create Maximum Number
Any answer takes some s digits from nums1 and k - s from nums2. For a fixed s, the best choice from each array is its lexicographically largest subsequence of that length, and the best interleaving of two sequences is a greedy merge that compares suffixes.
Approach
- For
sfrommax(0, k - n)tomin(k, m): - Pick the largest length-
ssubsequence ofnums1with a stack: for each digit, while digits may still be dropped and the top is smaller, pop; then push. Keep the firsts. Do the same fornums2withk - s. - Merge: repeatedly take the head of the sequence whose remaining suffix is lexicographically larger (a suffix that is a prefix of the other counts as smaller).
- Keep the largest merged array over all
sand return it.
Why it works
Fix how many digits come from each array. The merged number is maximised by maximising each part (a lexicographically larger part can never yield a smaller merge), and the stack produces the largest subsequence of a given length because each pop replaces a digit by a larger one at an earlier position. In the merge, comparing whole suffixes on a tie picks the array whose next differing digit is larger, which can only be reached sooner by taking from it first.
Complexity
- Time —
O(k · (m + n)^2) in the worst case - Space —
O(m + n)
Pitfalls
- On equal heads, comparing only the next digit is not enough — compare the full remaining suffixes (e.g.
[6,7]vs[6,0,4]). - The range of
sis limited by both lengths:max(0, k - n) <= s <= min(k, m). - In the stack, track how many digits may still be dropped; stop popping when that runs out.
Reference solution
Python
from typing import List
def maxNumber(nums1: List[int], nums2: List[int], k: int) -> List[int]:
def pick(a, t):
st = []
drop = len(a) - t
for x in a:
while drop > 0 and st and st[-1] < x:
st.pop()
drop -= 1
st.append(x)
return st[:t]
def merge(a, b):
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 = []
for s in range(max(0, k - n), min(k, m) + 1):
cand = merge(pick(nums1, s), pick(nums2, k - s))
if cand > best:
best = cand
return bestJava
private static int[] pickMaxMN(int[] a, int t) {
int[] st = new int[a.length];
int top = 0, drop = a.length - t;
for (int x : a) {
while (drop > 0 && top > 0 && st[top - 1] < x) { top--; drop--; }
st[top++] = x;
}
return Arrays.copyOf(st, t);
}
private static boolean greaterMN(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]);
}
public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length, n = nums2.length;
int[] best = new int[0];
for (int s = Math.max(0, k - n); s <= Math.min(k, m); s++) {
int[] a = pickMaxMN(nums1, s), b = pickMaxMN(nums2, k - s);
int[] cand = new int[k];
int i = 0, j = 0, p = 0;
while (i < a.length || j < b.length) {
if (greaterMN(a, i, b, j)) cand[p++] = a[i++];
else cand[p++] = b[j++];
}
if (greaterMN(cand, 0, best, 0)) best = cand;
}
return best;
}C++
static vector<int> pickMaxMN(const vector<int>& a, int t) {
vector<int> st;
int drop = (int)a.size() - t;
for (int x : a) {
while (drop > 0 && !st.empty() && st.back() < x) { st.pop_back(); drop--; }
st.push_back(x);
}
st.resize(t);
return st;
}
static bool greaterMN(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> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
vector<int> best;
for (int s = max(0, k - n); s <= min(k, m); s++) {
vector<int> a = pickMaxMN(nums1, s), b = pickMaxMN(nums2, k - s);
vector<int> cand;
int i = 0, j = 0;
while (i < (int)a.size() || j < (int)b.size()) {
if (greaterMN(a, i, b, j)) cand.push_back(a[i++]);
else cand.push_back(b[j++]);
}
if (greaterMN(cand, 0, best, 0)) best = cand;
}
return best;
}JavaScript
var maxNumber = function(nums1, nums2, k) {
var pickMax = function(a, t) {
var st = [], drop = a.length - t;
for (var i = 0; i < a.length; i++) {
while (drop > 0 && st.length > 0 && st[st.length - 1] < a[i]) { st.pop(); drop--; }
st.push(a[i]);
}
return st.slice(0, t);
};
var greater = function(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]);
};
var merge = function(a, b) {
var res = [], 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;
};
var m = nums1.length, n = nums2.length;
var best = [];
for (var s = Math.max(0, k - n); s <= Math.min(k, m); s++) {
var cand = merge(pickMax(nums1, s), pickMax(nums2, k - s));
if (greater(cand, 0, best, 0)) best = cand;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms