Problem Statement

Given two integer arrays nums1 and nums2 representing the digits of two numbers and an integer k, create the maximum number of length k <= m + n from digits of these two numbers while preserving the relative order of the digits from the same array. https://leetcode.com/problems/create-maximum-number/

Understanding the Problem

The problem is to merge two arrays into the largest possible number of length k using digits from both, while maintaining the order of digits as they appear in their respective arrays. A direct approach might attempt to combine the arrays in every possible way and check which combination yields the largest number, but this is inefficient for larger arrays.

Dynamic Programming Strategy: The Key to the Solution

The core idea involves:

  • Single Array Max Sequence Generation: For each array and for each possible sub-length, generate the maximum possible sequence of that length.
  • Merge with Order Preservation: Merge two sequences to form the largest possible number, respecting the order from both sequences.

Algorithmic Approach

  1. Max Single Array Function: A helper function to generate the maximum subsequence of length k for an array while preserving the order.
  2. Merge Function: A function to merge two sequences into the largest possible number.
  3. Main Function:
    • Iterate over all possible splits between nums1 and nums2 that sum to k.
    • Use the helper functions to get the best sequence from each part and merge them.
    • Track the largest sequence found.

Time and Space Complexity

  • Time Complexity: O((m + n) * k^2), because for each split, we compute maximum subsequences and merge them.
  • Space Complexity: O(k), as we are storing sequences up to length k.

Detailed Walkthrough of the Example

Example Input:

  • nums1 = [3,4,6,5]
  • nums2 = [9,1,2,5,8,3]
  • k = 5

Step 1: Max Single Number Generation

  • We need to generate the maximum subsequences for various lengths from each array using the maxSingleNumber function.

From nums1:

  • For k = 1: The maximum number possible from [3,4,6,5] is [6].
  • For k = 2: The maximum numbers possible are [6, 5].
  • For k = 3: The maximum numbers possible are [4, 6, 5].
  • For k = 4: The original sequence itself, [3, 4, 6, 5].

From nums2:

  • For k = 1: The maximum number is [9].
  • For k = 2: The maximum numbers are [9, 8].
  • For k = 3: The maximum numbers are [9, 8, 3] (since 3 is the last digit, it is taken to fill the sequence).
  • For k = 4: The maximum numbers are [9, 5, 8, 3].
  • For k = 5: The maximum numbers are [9, 2, 5, 8, 3].

Step 2: Merge Function

  • This function takes two arrays and merges them into the largest possible sequence, respecting the original order of each but choosing the largest possible leading number at each step.

Step 3: Combining Strategies

  • For each possible split of the total number k into two parts—one from nums1 and one from nums2—we generate maximum numbers and then merge them.

Combination Scenarios:

  • i = 0 and k-i = 5: Merge [] from nums1 and [9, 2, 5, 8, 3] from nums2.
  • i = 1 and k-i = 4: Merge [6] from nums1 and [9, 5, 8, 3] from nums2.
  • i = 2 and k-i = 3: Merge [6, 5] from nums1 and [9, 8, 3] from nums2.
  • i = 3 and k-i = 2: Merge [4, 6, 5] from nums1 and [9, 8] from nums2.
  • i = 4 and k-i = 1: Merge [3, 4, 6, 5] from nums1 and [9] from nums2.

Example Merge Operation:

Let’s illustrate one of these merges—i = 3 and k-i = 2:

  • First Number: Between [4, 6, 5] and [9, 8], the largest available first digit is 9.
  • Second Number: Now, we compare [4, 6, 5] and [8]. The next largest available is 8.
  • Remaining Numbers: Continue with [4, 6, 5].
  • Resulting Number: The merged number is [9, 8, 6, 5, 3].

Final Step: Choosing the Best Combination

  • Compare all the results from the different merges, and the final output is the largest sequence obtained, which in this walkthrough, and under correct implementation, would be [9, 8, 6, 5, 3].

Conclusion

This code efficiently finds the largest possible sequence by using dynamic programming principles and combinatorial strategies, considering all possible distributions of k between the two input arrays to find the optimal solution.

Code Implementation

function maxSingleNumber(nums, k) {
    const stack = [];
    let toRemove = nums.length - k;
    for (let num of nums) {
        while (stack.length && toRemove > 0 && stack[stack.length - 1] < num) {
            stack.pop();
            toRemove--;
        }
        stack.push(num);
    }
    return stack.slice(0, k);
}

function merge(nums1, nums2) {
    const result = [];
    while (nums1.length > 0 || nums2.length > 0) {
        if (nums1.length === 0) {
            result.push(nums2.shift());
        } else if (nums2.length === 0) {
            result.push(nums1.shift());
        } else if (nums1[0] > nums2[0]) {
            result.push(nums1.shift());
        } else if (nums1[0] < nums2[0]) {
            result.push(nums2.shift());
        } else {
            result.push(nums1 > nums2 ? nums1.shift() : nums2.shift());
        }
    }
    return result;
}

var maxNumber = function(nums1, nums2, k) {
    let maxResult = [];
    for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
        const maxNums1 = maxSingleNumber(nums1, i);
        const maxNums2 = maxSingleNumber(nums2, k - i);
        const currentMax = merge(maxNums1, maxNums2);
        if (maxResult < currentMax) {
            maxResult = currentMax;
        }
    }
    return maxResult;
};
<
Previous Post
Finding the Longest Increasing Subsequence in an Array
>
Blog Archive
Archive of all previous blog posts