LeetCode 321: Create Maximum Number Solution

Master LeetCode problem 321 (Create Maximum Number), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

321. Create Maximum Number

Hard

Array Two Pointers Stack Greedy Monotonic Stack

Problem Explanation

Explanation

To solve this problem, we can divide it into two subproblems:

Create the maximum number of length x from a single array while preserving the relative order of the digits.
Merge two maximum numbers created from the two arrays to form the final maximum number of length k.

For the first subproblem, we can use a stack to store the maximum number of length x by popping elements from the stack if a greater element is found. For the second subproblem, we can merge the two maximum numbers by comparing the elements at each position to pick the larger one.

By combining these two subproblems, we can create the maximum number of length k from the two arrays.

Time Complexity: O(k * (m + n)) where m and n are the lengths of the input arrays. Space Complexity: O(k) for storing the final result.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 321 (Create Maximum Number)?

This page provides optimized solutions for LeetCode problem 321 (Create Maximum Number) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 321 (Create Maximum Number)?

The time complexity for LeetCode 321 (Create Maximum Number) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 321 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 321 in Java, C++, or Python.

Back to LeetCode Solutions