Create maximum number

Array Two Pointers Stack Greedy Monotonic Stack

34.7% acceptance

Jan 12, 2026

2121

375

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k. Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved. Return an array of the k digits representing the answer.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_number(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let m = nums1.len();
    let n = nums2.len();
    
    fn max_array(nums: &[i32], k: usize) -> Vec<i32> {
      let mut stack = Vec::new();
      let mut drop = nums.len() - k;
      
      for &num in nums {
        while !stack.is_empty() && *stack.last().unwrap() < num && drop > 0 {
          stack.pop();
          drop -= 1;
        }
        stack.push(num);
      }
      
      stack.into_iter().take(k).collect()
    }
    
    fn merge(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
      let mut result = Vec::new();
      let mut i = 0;
      let mut j = 0;
      
      while i < nums1.len() || j < nums2.len() {
        if i < nums1.len() && (j >= nums2.len() || &nums1[i..] > &nums2[j..]) {
          result.push(nums1[i]);
          i += 1;
        } else {
          result.push(nums2[j]);
          j += 1;
        }
      }
      
      result
    }
    
    let mut result = vec![];
    let start = if k > n { k - n } else { 0 };
    let end = k.min(m);
    
    for i in start..=end {
      let arr1 = max_array(&nums1, i);
      let arr2 = max_array(&nums2, k - i);
      let merged = merge(&arr1, &arr2);
      if merged > result {
        result = merged;
      }
    }
    
    result
  }
}