321. Create Maximum Number LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 321. Create Maximum Number LeetCode Solution with the best time and space complexity. The solution to Create Maximum Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Create Maximum Number solution in C++
Create Maximum Number solution in Java
Create Maximum Number solution in Python
Additional Resources

321. Create Maximum Number LeetCode Solution image

Problem Statement of Create Maximum Number

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.

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]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

Constraints:

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n
nums1 and nums2 do not have leading zeros.

Complexity Analysis

Time Complexity: O(k(m + n)^2)
Space Complexity: O(m + n)

321. Create Maximum Number LeetCode Solution in C++

class Solution {
 public:
  vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<int> ans;

    for (int k1 = 0; k1 <= k; ++k1) {
      const int k2 = k - k1;
      if (k1 > nums1.size() || k2 > nums2.size())
        continue;
      ans = max(ans, merge(maxArray(nums1, k1), maxArray(nums2, k2)));
    }

    return ans;
  }

 private:
  vector<int> maxArray(const vector<int>& nums, int k) {
    vector<int> res;
    int toPop = nums.size() - k;
    for (const int num : nums) {
      while (!res.empty() && res.back() < num && toPop-- > 0)
        res.pop_back();
      res.push_back(num);
    }
    return {res.begin(), res.begin() + k};
  }

  // Merges nums1 and nums2.
  vector<int> merge(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> res;
    auto s1 = nums1.cbegin();
    auto s2 = nums2.cbegin();
    while (s1 != nums1.cend() || s2 != nums2.cend())
      if (lexicographical_compare(s1, nums1.cend(), s2, nums2.cend()))
        res.push_back(*s2++);
      else
        res.push_back(*s1++);
    return res;
  }
};
/* code provided by PROGIEZ */

321. Create Maximum Number LeetCode Solution in Java

class Solution {
  public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int[] ans = new int[k];

    for (int k1 = 0; k1 <= k; ++k1) {
      final int k2 = k - k1;
      if (k1 > nums1.length || k2 > nums2.length)
        continue;
      int[] candidate = merge(maxArray(nums1, k1), maxArray(nums2, k2));
      if (greater(candidate, 0, ans, 0))
        ans = candidate;
    }
    return ans;
  }

  private int[] maxArray(int[] nums, int k) {
    List<Integer> res = new ArrayList<>();
    int toPop = nums.length - k;
    for (final int num : nums) {
      while (!res.isEmpty() && res.get(res.size() - 1) < num && toPop > 0) {
        res.remove(res.size() - 1);
        --toPop;
      }
      res.add(num);
    }
    return res.subList(0, k).stream().mapToInt(Integer::intValue).toArray();
  }

  // Merges nums1 and nums2.
  private int[] merge(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length + nums2.length];
    for (int i = 0, j = 0, k = 0; k < res.length; ++k)
      res[k] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
    return res;
  }

  // Returns true if nums1[i..n) > nums2[j..n).
  private boolean greater(int[] nums1, int i, int[] nums2, int j) {
    while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
      ++i;
      ++j;
    }
    return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
  }
}
// code provided by PROGIEZ

321. Create Maximum Number LeetCode Solution in Python

class Solution:
  def maxNumber(self, nums1: list[int], nums2: list[int], k: int) -> list[int]:
    def maxArray(nums: list[int], k: int) -> list[int]:
      res = []
      toTop = len(nums) - k
      for num in nums:
        while res and res[-1] < num and toTop > 0:
          res.pop()
          toTop -= 1
        res.append(num)
      return res[:k]

    def merge(nums1: list[int], nums2: list[int]) -> list[int]:
      return [max(nums1, nums2).pop(0) for _ in nums1 + nums2]

    return max(merge(maxArray(nums1, i), maxArray(nums2, k - i))
               for i in range(k + 1)
               if i <= len(nums1) and k - i <= len(nums2))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents