Last updated on July 20th, 2024 at 04:22 am

Here, We see Create Maximum Number LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Dynamic Programming, Greedy

Companies

Google

Level of Question

Hard

Create Maximum Number LeetCode Solution

Problem Statement

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]

1. Create Maximum Number LeetCode Solution C++

class Solution {
  public: vector < int > maxNumber(vector < int > & nums1, vector < int > & nums2, int k) {
    int n1 = nums1.size(), n2 = nums2.size();
    vector < int > best;
    for (int k1 = max(k - n2, 0); k1 <= min(k, n1); ++k1)
      best = max(best, maxNumber(maxNumber(nums1, k1),
        maxNumber(nums2, k - k1)));
    return best;
  }
  vector < int > maxNumber(vector < int > nums, int k) {
    int drop = nums.size() - k;
    vector < int > out;
    for (int num: nums) {
      while (drop && out.size() && out.back() < num) {
        out.pop_back();
        drop--;
      }
      out.push_back(num);
    }
    out.resize(k);
    return out;
  }
  vector < int > maxNumber(vector < int > nums1, vector < int > nums2) {
    vector < int > out;
    while (nums1.size() + nums2.size()) {
      vector < int > & now = nums1 > nums2 ? nums1 : nums2;
      out.push_back(now[0]);
      now.erase(now.begin());
    }
    return out;
  }
};

2. Create Maximum Number LeetCode Solution Java

class Solution {
  public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int n = nums1.length;
    int m = nums2.length;
    int[] ans = new int[k];
    for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
      int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
      if (greater(candidate, 0, ans, 0)) ans = candidate;
    }
    return ans;
  }
  private int[] merge(int[] nums1, int[] nums2, int k) {
    int[] ans = new int[k];
    for (int i = 0, j = 0, r = 0; r < k; ++r)
      ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
    return ans;
  }
  public 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]);
  }
  public int[] maxArray(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[k];
    for (int i = 0, j = 0; i < n; ++i) {
      while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
      if (j < k) ans[j++] = nums[i];
    }
    return ans;
  }
}

3. Create Maximum Number Solution JavaScript

var maxNumber = function(nums1, nums2, k) {
	const maxArray = (nums, k) => {
		const stack = [];
		let popCount = nums.length - k;
		for (const num of nums) {
			while (popCount > 0 && stack.length && stack[stack.length - 1] < num) {
				stack.pop();
				popCount--;
			}
			stack.push(num);
		}
		return stack.slice(0, k);
	};
	const mergeArrays = (arr1, arr2) => {
		const merged = [];
		while (arr1.length || arr2.length) {
			const bigger = arr1 > arr2 ? arr1 : arr2;
			merged.push(bigger.shift());
		}
		return merged;
	};
	let max = [];
	for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
		const merged = mergeArrays(maxArray(nums1, i), maxArray(nums2, k - i));
		if (merged > max) max = merged;
	}
	return max;
};

4. Create Maximum Number Solution Python

class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        def prep(nums, k):
            drop = len(nums) - k
            out = []
            for num in nums:
                while drop and out and out[-1] < num:
                    out.pop()
                    drop -= 1
                out.append(num)
            return out[:k]
        def merge(a, b):
            return [max(a, b).pop(0) for _ in a + b]
        return max(
            merge(prep(nums1, i), prep(nums2, k - i))
            for i in range(k + 1)
            if i <= len(nums1) and k - i <= len(nums2)
        )