Problem overview
The function max_number receives two vectors of digits, nums1 and nums2, and an integer k. It must build the largest possible number of exactly k digits by picking digits from the two vectors. Digits taken from the same vector must stay in their original order, but the picks from the two vectors can be interleaved freely. The result is a Vec<i32> of the k digits.
For nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3] and k = 5 the answer is [9, 8, 6, 5, 3]. It takes 9 and 8 and 3 from nums2, and 6 and 5 from nums1. For [6, 7], [6, 0, 4] and k = 5 every digit is used and the answer is [6, 7, 6, 0, 4].
Approach: split, shrink each side, merge, compare
Any answer takes some number i of digits from nums1 and the other k - i from nums2. So the plan is to try every split and keep the best result. For one split, the problem breaks into three smaller parts:
- The best
i-digit number fromnums1that keeps the digits in order. - The best
(k - i)-digit number fromnums2. - The best merge of those two numbers into one number of
kdigits.
The first two use a stack, the idea behind Remove K Digits turned around: while scanning, a bigger digit pops smaller digits before it, because moving a bigger digit left makes the number larger. The pop is allowed only if enough digits remain to still fill size places: stack.len() + nums.len() - i > size.
The merge is the subtle part. Taking the larger of the two next digits isn't enough when they are equal. For [6, 7] and [6, 0, 4], both lists start with 6. The 6 must come from the first list, because then 7 comes next and beats 0. Taking the 6 from the second list would give [6, 6, 7, 0, 4], which is smaller than [6, 7, 6, 0, 4]. So the merge compares everything that is left of each list: it skips equal digits until they differ, and the list with the bigger digit there goes first. If one list runs out during the comparison, the longer one wins.
The same comparison picks the best candidate across splits. All candidates have k digits, so the first different digit decides which is bigger.
Step by step
- Convert
ktousizeby shadowing it, because lengths and indexes areusize. - Create
bestas an emptyVec<i32>. Any candidate beats an empty list. - Loop
iover0..=k. This is how many digits come fromnums1. - Skip impossible splits. Both
i <= nums1.len()andk - i <= nums2.len()must hold. - Compute
firstandsecondwithmax_subsequence. - Merge them into
candidatewithmerge. - Keep the larger one: if
is_greatersays the candidate beatsbest, replace it. - Return
best. - Write
max_subsequence, taking a slice and a size. - Create the stack of kept digits.
- Loop over the indexes of
nums, since the index tells how many digits remain. - Pop smaller digits while the top is smaller than
nums[i]and dropping it still leaves enough digits. - Pop the top.
- Push the digit if the stack holds fewer than
sizedigits. - Return the stack.
- Write
merge, taking two slices. - Create
result. - Create the indexes
iandjat 0 with one tuple pattern. - Loop while either list has digits. Each turn takes exactly one digit.
- Compare what is left with
is_greater(a, i, b, j). - Take from
aand advancei. - Otherwise take from
band advancej. When the remainders are equal, either choice gives the same number. - Return
result. - Write
is_greater, with mutable start indexes. - Skip equal digits while both lists have digits and they match.
- Advance both indexes.
- Return who wins:
bran out, orastill has a bigger digit.
The solution in Rust
impl Solution {
fn max_number(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<i32> {
let k = k as usize;
let mut best: Vec<i32> = Vec::new();
for i in 0..=k {
if i <= nums1.len() && k - i <= nums2.len() {
let first = Self::max_subsequence(&nums1, i);
let second = Self::max_subsequence(&nums2, k - i);
let candidate = Self::merge(&first, &second);
if Self::is_greater(&candidate, 0, &best, 0) {
best = candidate;
}
}
}
best
}
fn max_subsequence(nums: &[i32], size: usize) -> Vec<i32> {
let mut stack: Vec<i32> = Vec::new();
for i in 0..nums.len() {
while !stack.is_empty() && *stack.last().unwrap() < nums[i] && stack.len() + nums.len() - i > size {
stack.pop();
}
if stack.len() < size {
stack.push(nums[i]);
}
}
stack
}
fn merge(a: &[i32], b: &[i32]) -> Vec<i32> {
let mut result: Vec<i32> = Vec::new();
let (mut i, mut j) = (0, 0);
while i < a.len() || j < b.len() {
if Self::is_greater(a, i, b, j) {
result.push(a[i]);
i += 1;
} else {
result.push(b[j]);
j += 1;
}
}
result
}
fn is_greater(a: &[i32], mut i: usize, b: &[i32], mut j: usize) -> bool {
while i < a.len() && j < b.len() && a[i] == b[j] {
i += 1;
j += 1;
}
j == b.len() || (i < a.len() && a[i] > b[j])
}
}
The Rust details worth a look:
- Unsigned arithmetic stays safe. In
k - i,inever exceedsk, because the loop is0..=k. Instack.len() + nums.len() - i, Rust adds first and subtracts after, andiis belownums.len(), so the result never goes below zero. - Borrowing a vector as a slice. The helpers take
&[i32]. Passing&nums1, a&Vec<i32>, works because Rust converts it to a slice. The helpers read the digits and never need to own them. best = candidatemoves the vector.candidateisn't used afterwards, so no copy is made. The callis_greater(&candidate, 0, &best, 0)only borrows both, and the borrows end before the assignment.let (mut i, mut j) = (0, 0)declares two mutable variables at once. They are compared withlen(), so Rust infersusize.mut i: usizein a parameter makesis_greaterown a private, changeable copy of the start index. The caller's index doesn't move.- Empty comparisons.
is_greaterwith an emptybreturns true at once, becausej == b.len(). That is why the first candidate always replaces the emptybest. Inmerge, whenahas run out andbhasn't, the test is false, so the else branch readsb[j], which is in range. - Indexing panics out of range. In
mergethea[i]read only happens whenis_greateris true, which impliesi < a.len()as long as the loop condition holds.
Complexity
Time. There are at most min(m, n) + 1 valid splits. For each, max_subsequence costs O(m + n) in total, because every digit is pushed and popped at most once. The merge takes k steps, and each step's is_greater may scan up to k digits, so one merge is O(k²) in the worst case, such as when all digits are equal. An upper bound for the whole function is O(min(m, n) · (m + n)²). Typical inputs stop comparing after a digit or two, so they run much faster than this bound.
Space: O(m + n). The two subsequences, the merged candidate and best each hold at most k digits.
Edge cases and common mistakes
- A split with zero digits from one side.
i = 0ori = kis valid.max_subsequencewith size 0 never pushes, so it returns an empty vector, and the merge copies the other side. - Splits that can't happen. If
k - iis bigger thannums2.len(), the split is skipped. Without the check,max_subsequencewould return fewer digits than requested. - Comparing only the next digits in the merge. For
[6, 7]and[6, 0, 4]this produces[6, 6, 7, 0, 4], which is wrong. Comparing the remainders gives[6, 7, 6, 0, 4]. - Popping without the length guard. Without
stack.len() + nums.len() - i > size, the stack could pop digits that are needed to reachsizeand end up too short. - Zeros. Digits are 0 to 9, and a result such as
[0, 0]is valid: for[0],[0]andk = 2the answer is[0, 0]. Nothing is stripped. - Using the biggest digit blindly. For
[5, 1],[9]andk = 2the answer is[9, 5], not[9, 1]: the split with one digit from each side wins, and each side keeps its own best digit.
Testing
nums1 = [3, 4, 6, 5],nums2 = [9, 1, 2, 5, 8, 3],k = 5gives[9, 8, 6, 5, 3].nums1 = [6, 7],nums2 = [6, 0, 4],k = 5gives[6, 7, 6, 0, 4].nums1 = [3, 9],nums2 = [8, 9],k = 3gives[9, 8, 9].nums1 = [0],nums2 = [0],k = 2gives[0, 0].nums1 = [5, 1],nums2 = [9],k = 1gives[9].
