We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Create Maximum Number

Difficulty: Hard

Problem Description

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.

Key Insights

  • We need to select a total of k digits from both arrays while preserving the order.
  • We can use a greedy approach to select the largest possible digits first, ensuring that we do not exceed the required length of k.
  • The combination of digits from both arrays must be merged in a way that results in the highest possible number.

Space and Time Complexity

Time Complexity: O(m + n + k^2)
Space Complexity: O(k)

Solution

The solution involves two main steps:

  1. Selecting the Maximum Subarray: For each array, we need to create a maximum subarray of a certain length while maintaining the order of elements. This can be achieved using a monotonic stack approach, where we iterate through the array and maintain a stack that stores the current maximum sequence of digits.

  2. Merging the Two Subarrays: After obtaining the maximum subarrays from nums1 and nums2, we need to merge them to form the largest possible number. This is done by comparing the current elements of both subarrays and choosing the larger one to maintain the maximum value.

Code Solutions

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

    def merge(arr1, arr2):
        return [max(arr1, arr2).pop(0) for _ in range(len(arr1) + len(arr2))]

    max_result = []
    for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
        part1 = maxSubArray(nums1, i)
        part2 = maxSubArray(nums2, k - i)
        max_result = max(max_result, merge(part1, part2))
    
    return max_result
← Back to All Questions