321. Create Maximum Number - Leetcode Solution

Code Implementation

class Solution:
    def maxNumber(self, nums1, nums2, k):
        def pickMax(nums, k):
            stack = []
            drop = len(nums) - k
            for num in nums:
                while drop and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:k]

        def merge(nums1, nums2):
            res = []
            while nums1 or nums2:
                # Compare lexicographically
                if nums1 > nums2:
                    res.append(nums1.pop(0))
                else:
                    res.append(nums2.pop(0))
            return res

        max_num = []
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
            pick1 = pickMax(nums1, i)
            pick2 = pickMax(nums2, k - i)
            merged = merge(pick1[:], pick2[:])
            if merged > max_num:
                max_num = merged
        return max_num

class Solution {
public:
    vector<int> pickMax(vector<int>& nums, int k) {
        vector<int> stack;
        int drop = nums.size() - k;
        for (int num : nums) {
            while (drop && !stack.empty() && stack.back() < num) {
                stack.pop_back();
                drop--;
            }
            stack.push_back(num);
        }
        stack.resize(k);
        return stack;
    }
    
    bool greater(vector<int>& nums1, int i, vector<int>& nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            i++; j++;
        }
        return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
    }
    
    vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        int i = 0, j = 0;
        while (i < nums1.size() || j < nums2.size()) {
            if (greater(nums1, i, nums2, j))
                res.push_back(nums1[i++]);
            else
                res.push_back(nums2[j++]);
        }
        return res;
    }
    
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> max_num;
        int m = nums1.size(), n = nums2.size();
        for (int i = max(0, k - n); i <= min(k, m); ++i) {
            vector<int> pick1 = pickMax(nums1, i);
            vector<int> pick2 = pickMax(nums2, k - i);
            vector<int> merged = merge(pick1, pick2);
            if (merged > max_num)
                max_num = merged;
        }
        return max_num;
    }
};

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] maxNum = new int[k];
        int m = nums1.length, n = nums2.length;
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); ++i) {
            int[] pick1 = pickMax(nums1, i);
            int[] pick2 = pickMax(nums2, k - i);
            int[] merged = merge(pick1, pick2);
            if (greater(merged, 0, maxNum, 0)) {
                maxNum = merged;
            }
        }
        return maxNum;
    }
    
    private int[] pickMax(int[] nums, int k) {
        int[] stack = new int[k];
        int top = -1, drop = nums.length - k;
        for (int num : nums) {
            while (top >= 0 && drop > 0 && stack[top] < num) {
                top--;
                drop--;
            }
            if (top + 1 < k) {
                stack[++top] = num;
            } else {
                drop--;
            }
        }
        return stack;
    }
    
    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]);
    }
    
    private int[] merge(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length + nums2.length];
        int i = 0, j = 0, r = 0;
        while (i < nums1.length || j < nums2.length) {
            if (greater(nums1, i, nums2, j))
                res[r++] = nums1[i++];
            else
                res[r++] = nums2[j++];
        }
        return res;
    }
}

var maxNumber = function(nums1, nums2, k) {
    function pickMax(nums, k) {
        let stack = [];
        let drop = nums.length - k;
        for (let num of nums) {
            while (drop && stack.length && stack[stack.length - 1] < num) {
                stack.pop();
                drop--;
            }
            stack.push(num);
        }
        return stack.slice(0, k);
    }
    
    function greater(nums1, i, nums2, 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]);
    }
    
    function merge(nums1, nums2) {
        let res = [];
        let i = 0, j = 0;
        while (i < nums1.length || j < nums2.length) {
            if (greater(nums1, i, nums2, j))
                res.push(nums1[i++]);
            else
                res.push(nums2[j++]);
        }
        return res;
    }
    
    let maxNum = [];
    let m = nums1.length, n = nums2.length;
    for (let i = Math.max(0, k - n); i <= Math.min(k, m); ++i) {
        let pick1 = pickMax(nums1, i);
        let pick2 = pickMax(nums2, k - i);
        let merged = merge(pick1, pick2);
        if (merged.join('') > maxNum.join(''))
            maxNum = merged;
    }
    return maxNum;
};

Problem Description

You are given two arrays of digits, nums1 and nums2, and an integer k. Your task is to create the largest possible number of length k by selecting digits from nums1 and nums2 while maintaining the relative order of digits from each array. You may select any number of digits from either array, as long as the total count is exactly k. Each element from the arrays can be used at most once and must not be reused.

The result should be the lexicographically largest possible number (as an array of digits). There is only one valid solution for each input.

Thought Process

At first glance, you might think to try all possible ways of picking k digits by combining digits from nums1 and nums2, and then select the largest one. However, this approach would be far too slow, especially if the arrays are large, because the number of possible combinations grows rapidly.

The next step is to realize that we can break the problem into smaller parts: for each possible split (taking i digits from nums1 and k - i from nums2), we can find the largest subsequence of length i from nums1 and k-i from nums2. Then, by merging these two subsequences optimally, we can get a candidate answer. We repeat this for all possible splits and keep the best result.

The key insight is to use a greedy approach for picking the largest subsequence from one array (using a stack-like method), and to merge two sequences so that the result is lexicographically maximal.

Solution Approach

Step 1: Try All Splits
For every possible split (i.e., take i digits from nums1 and k-i from nums2), where i ranges from max(0, k - len(nums2)) to min(k, len(nums1)):
- We ensure we do not take more digits than available in either array.
Step 2: Pick the Maximum Subsequence from Each Array
For each split, pick the largest subsequence of length i from nums1 and length k-i from nums2. This is done using a monotonic stack approach:
- Iterate through the array, and for each element, pop the stack if the current element is greater and we still have digits we can drop.
- This ensures we keep the largest possible digits in order.
Step 3: Merge the Two Subsequences
Merge the two picked subsequences to form the largest possible number. At each step, pick the greater of the remaining digits from either array (lexicographically).
Step 4: Track the Maximum
After each merge, compare with the best result seen so far and keep the larger one.
Step 5: Return the Best Result
After trying all splits, return the largest number found.

We use helper functions for picking the maximum subsequence and merging, both of which are essential to the efficiency and correctness of the solution.

Example Walkthrough

Let's say nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], and k = 5.

Try all splits:
Possible splits are:
- Take 0 from nums1, 5 from nums2
- Take 1 from nums1, 4 from nums2
- Take 2 from nums1, 3 from nums2
- Take 3 from nums1, 2 from nums2
- Take 4 from nums1, 1 from nums2
For each split, pick the max subsequence:
For example, for 2 from nums1 and 3 from nums2:
- Pick max 2 from [3, 4, 6, 5] → [6, 5]
- Pick max 3 from [9, 1, 2, 5, 8, 3] → [9, 8, 3]
Merge:
Merge [6, 5] and [9, 8, 3] → Compare 6 and 9: 9 is bigger, so pick 9. Then compare 6 and 8: 8 is bigger, pick 8, etc. The merged result is [9, 8, 6, 5, 3].
Track the best:
Repeat for all splits and keep the largest result.
Final answer:
The largest number you can create is [9, 8, 6, 5, 3].

Time and Space Complexity

Brute-force approach: Would require generating all possible combinations of k digits from both arrays, which is exponential in time and infeasible for large arrays.

Optimized approach:

For each split (there are at most min(k, len(nums1)) - max(0, k - len(nums2)) + 1 splits), we:
- Pick the max subsequence from each array: O(n) for each array.
- Merge two arrays: O(k) time.
So, the total time complexity is O(k * (m + n + k)), where m and n are the lengths of nums1 and nums2.
Space complexity is O(k) for the result and temporary arrays.

Summary

The problem is solved by considering all valid ways to split the selection of digits between the two arrays, greedily picking the largest possible subsequence from each, and merging them in a way that preserves the maximal lexicographical order. The key insights are the use of a monotonic stack to efficiently pick the largest subsequence and a careful merge function. This makes the solution both efficient and elegant, avoiding brute-force enumeration of all possible combinations.

AlgoMap.io

Want Help Cracking FAANG?