LeetCode Solutions Blog

Create Maximum Number

Number: 321

Difficulty: Hard

Paid? No

Problem Description

Given two integer arrays representing digits of two numbers and an integer k, create the maximum number (as an array of digits) of length k by selecting digits from both arrays while preserving the relative order within each array.

Key Insights

Use a greedy, monotonic stack approach to select the maximum subsequence of a given length from a single array.
Merge two maximum subsequences by lexicographically comparing their remaining parts.
Try all possible splits of k digits between the two arrays to ensure the overall maximum is obtained.

Space and Time Complexity

Time Complexity: O((m+n) * k²) in the worst case due to iterating splits and comparing subsequences during merging
Space Complexity: O(k) for storing subsequences and the merged result

Solution

The solution consists of three main steps:

For each array, utilize a helper function to compute the maximum subsequence of a given length using a monotonic stack. This guarantees that the highest possible digits are chosen while preserving order.
Merge two subsequences into the maximum possible result by repeatedly selecting the lexicographically larger sequence among the remaining parts.
Iterate over all valid ways to split k between the two arrays (from max(0, k - length(nums2)) to min(k, length(nums1))) and record the best merged result.

Data structures employed include arrays and stacks. The algorithmic approach is greedy and leverages lexicographical comparison to merge sequences optimally.

Code Solutions

def maxNumber(nums1, nums2, k):
    # Helper function to get the maximum subsequence of given length t from array nums
    def getMaxSubsequence(nums, t):
        drop = len(nums) - t  # Number of elements that can be dropped
        stack = []
        for num in nums:
            # Remove smaller digits when possible to achieve a larger leading number
            while drop and stack and stack[-1] < num:
                stack.pop()
                drop -= 1
            stack.append(num)
        # Limit the result to length t
        return stack[:t]
    
    # Helper function to merge two subsequences into the maximum possible number
    def merge(seq1, seq2):
        merged = []
        while seq1 or seq2:
            # Lexicographical comparison of remaining parts
            if seq1 > seq2:
                merged.append(seq1[0])
                seq1 = seq1[1:]
            else:
                merged.append(seq2[0])
                seq2 = seq2[1:]
        return merged

    max_combo = []
    m, n = len(nums1), len(nums2)
    # Iterate over all possible splits: select i digits from nums1 and k-i from nums2
    for i in range(max(0, k - n), min(k, m) + 1):
        subseq1 = getMaxSubsequence(nums1, i)
        subseq2 = getMaxSubsequence(nums2, k - i)
        candidate = merge(subseq1, subseq2)
        if candidate > max_combo:
            max_combo = candidate
    return max_combo

# Example usage:
print(maxNumber([3,4,6,5], [9,1,2,5,8,3], 5))  # Expected Output: [9,8,6,5,3]