321. Create Maximum Number – Leetcode Solutions

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]

class Solution:
    def maxNumber(self, nums1, nums2, k):
        # Helper function to get the maximum subsequence of length 'length' from nums
        def get_max_subsequence(nums, length):
            drop = len(nums) - length  # Number of elements we can drop
            stack = []
            for num in nums:
                # Discard smaller elements to make room for larger ones
                while drop > 0 and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            # Return the largest subsequence of the required length
            return stack[:length]
        
        # Helper function to merge two subsequences into the largest possible sequence
        def merge(subseq1, subseq2):
            return [max(subseq1, subseq2).pop(0) for _ in range(len(subseq1) + len(subseq2))]
        
        # Result to store the maximum number formed
        max_num = []
        
        # Try all possible splits where i elements are taken from nums1 and (k - i) from nums2
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
            subseq1 = get_max_subsequence(nums1, i)  # Max subsequence of length i from nums1
            subseq2 = get_max_subsequence(nums2, k - i)  # Max subsequence of length k-i from nums2
            # Merge the subsequences and check if the result is better
            max_num = max(max_num, merge(subseq1, subseq2))
        
        return max_num

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // Function to find the maximum subsequence of length t from the input array
    vector<int> maxSubsequence(vector<int>& nums, int t) {
        vector<int> result;
        int toRemove = nums.size() - t; // Calculate how many elements can be removed

        // Iterate through the array and construct the maximum subsequence
        for (int num : nums) {
            // Remove elements from the result if they are smaller than the current element
            // and we still have elements to remove
            while (!result.empty() && result.back() < num && toRemove > 0) {
                result.pop_back();
                toRemove--;
            }
            result.push_back(num);
        }

        // We may have extra elements if we didn't remove enough, so resize the vector
        result.resize(t);
        return result;
    }

    // Function to merge two subsequences into the largest possible sequence
    vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
        vector<int> merged;

        // Compare two sequences lexicographically and choose the larger one element by element
        while (!nums1.empty() || !nums2.empty()) {
            if (nums1 > nums2) {
                merged.push_back(nums1.front());
                nums1.erase(nums1.begin());
            } else {
                merged.push_back(nums2.front());
                nums2.erase(nums2.begin());
            }
        }
        return merged;
    }

    // Main function to find the maximum number of length k from nums1 and nums2
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> maxResult;

        // Try all possible ways of splitting the subsequences from nums1 and nums2
        for (int i = max(0, k - (int)nums2.size()); i <= min(k, (int)nums1.size()); i++) {
            vector<int> subseq1 = maxSubsequence(nums1, i);          // Get the best subsequence of length i from nums1
            vector<int> subseq2 = maxSubsequence(nums2, k - i);      // Get the best subsequence of length k - i from nums2
            vector<int> candidate = merge(subseq1, subseq2);         // Merge the two subsequences
            
            // Update the result if the current candidate is better
            if (candidate > maxResult) {
                maxResult = candidate;
            }
        }

        return maxResult;  // Return the best possible sequence
    }
};

var maxNumber = function(nums1, nums2, k) {
    // Function to get the maximum subarray of length "len" from nums
    const maxSubarray = (nums, len) => {
        let stack = [];
        let drop = nums.length - len; // Number of elements we can drop to get the subarray of size "len"
        
        for (let num of nums) {
            // If the current number is greater than the top of the stack and we can drop more elements, pop the stack
            while (drop > 0 && stack.length > 0 && stack[stack.length - 1] < num) {
                stack.pop();
                drop--;
            }
            stack.push(num);
        }
        // Only keep the first "len" elements in the stack, as it may have extra elements
        return stack.slice(0, len);
    };

    // Function to merge two subarrays to form the maximum number
    const merge = (sub1, sub2) => {
        let result = [];
        while (sub1.length || sub2.length) {
            // Compare the arrays lexicographically. If sub1 > sub2, take from sub1, else from sub2
            if (sub1 > sub2) {
                result.push(sub1.shift());
            } else {
                result.push(sub2.shift());
            }
        }
        return result;
    };

    let maxResult = [];
    
    // Try all possible splits of k between nums1 and nums2
    // i is the number of elements to take from nums1, and the rest will be taken from nums2
    for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
        let sub1 = maxSubarray(nums1, i);         // Get the best i-length subarray from nums1
        let sub2 = maxSubarray(nums2, k - i);     // Get the best (k - i)-length subarray from nums2
        let candidate = merge(sub1, sub2);        // Merge the two subarrays
        
        // Compare the current candidate with the best result so far, and update if it's better
        if (candidate > maxResult) {
            maxResult = candidate;
        }
    }
    
    return maxResult;
};

class Solution {
    
    // Main function to find the maximum number of length k
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        
        // Result array to store the final output
        int[] result = new int[k];
        
        // Try to pick i digits from nums1 and (k - i) digits from nums2
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
            // Get the maximum subsequence of length i from nums1
            int[] subsequence1 = maxSubsequence(nums1, i);
            
            // Get the maximum subsequence of length (k - i) from nums2
            int[] subsequence2 = maxSubsequence(nums2, k - i);
            
            // Merge both subsequences to form the largest possible number
            int[] candidate = merge(subsequence1, subsequence2);
            
            // Compare the candidate number with the current result
            if (greater(candidate, 0, result, 0)) {
                result = candidate; // Update result if candidate is greater
            }
        }
        return result; // Return the largest number of length k
    }
    
    // Helper function to find the maximum subsequence of length len from an array
    private int[] maxSubsequence(int[] nums, int len) {
        int[] subsequence = new int[len];
        int index = 0;
        int drop = nums.length - len; // Number of digits we can drop
        
        for (int num : nums) {
            // Greedily pick the largest digits while maintaining the order
            while (index > 0 && drop > 0 && subsequence[index - 1] < num) {
                index--; // Drop the smaller element
                drop--;
            }
            if (index < len) {
                subsequence[index++] = num; // Add the current digit to the subsequence
            } else {
                drop--; // Drop the current digit if we already have enough
            }
        }
        return subsequence;
    }
    
    // Helper function to merge two subsequences into the largest possible number
    private int[] merge(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        
        // Compare elements from both subsequences and pick the larger one
        while (i < nums1.length || j < nums2.length) {
            if (greater(nums1, i, nums2, j)) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        return merged;
    }
    
    // Helper function to compare two subsequences starting from indices i and j
    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 true if nums1 is greater starting from index i, otherwise false
        return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
    }
}