#321

Hard

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Create Maximum Number

Create Maximum Number involves merging digits from two arrays while preserving order, maximizing the resulting number.

array two pointers stack greedy monotonic stack

Problem Statement

You are given two integer arrays nums1 and nums2 of lengths m and n, respectively, and an integer k. Your task is to form the maximum number of length k from the digits of nums1 and nums2 while preserving the relative order of digits in each array.

Return an array of the k digits that represents the maximum number possible, where the digits are chosen from both arrays. The relative order of digits from the same array must remain unchanged.

Examples

Example 1

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

Output: [9,8,6,5,3]

Example details omitted.

Example 2

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5

Output: [6,7,6,0,4]

Example details omitted.

Example 3

Input: nums1 = [3,9], nums2 = [8,9], k = 3

Output: [9,8,9]

Example details omitted.

Constraints

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n
nums1 and nums2 do not have leading zeros.

Solution Approach

Two-Pointer Merging with Invariant Tracking

The key approach is to merge digits from both arrays using two pointers, ensuring that the relative order is preserved. At each step, we choose the larger possible digit while maintaining the order from each array. By tracking the remaining digits efficiently, this method ensures the largest possible number.

Greedy Selection with Monotonic Stack

Using a monotonic stack helps to efficiently choose the largest digits. The stack maintains the order and allows us to push and pop digits greedily, ensuring that we always pick the next largest digit that contributes to maximizing the final number.

Combining Results from Two Arrays

After selecting the maximum digits from each array, merge the results. This involves picking the optimal digits from nums1 and nums2 based on the two-pointer approach and ensuring that the order is maximized. The result is a merged number of length k.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach chosen, but a typical solution with two-pointer scanning will have a time complexity of O(m + n), where m and n are the lengths of nums1 and nums2, respectively. The space complexity is also O(m + n), due to the space required to store the resulting array and intermediate calculations.

What Interviewers Usually Probe

The candidate demonstrates understanding of two-pointer scanning and invariant tracking.
The candidate can articulate why a greedy approach works in this problem and how monotonic stacks are used.
The candidate shows ability to merge results from multiple arrays while maintaining order and maximizing the result.

Common Pitfalls or Variants

Common pitfalls

Failing to maintain the relative order of digits from each array.
Choosing digits greedily without considering the impact on future selections.
Incorrectly merging the two arrays and not adjusting the pointer positions properly.

Follow-up variants

Problem with larger arrays where the number k is near the total length of nums1 and nums2.
A version where only one array is non-empty.
A variation where the target number length k is smaller than the combined length of nums1 and nums2.

FAQ

How can I efficiently merge two arrays to create the maximum number?

Use a two-pointer approach combined with a monotonic stack to select the largest digits while maintaining the relative order of the arrays.

What are common mistakes when solving Create Maximum Number?

Common mistakes include failing to maintain the relative order of digits and greedy selection without considering future choices.

What is the time complexity of the Create Maximum Number problem?

The time complexity is typically O(m + n), where m and n are the lengths of the input arrays nums1 and nums2.

What is the pattern for solving Create Maximum Number?

The pattern involves using two-pointer scanning with invariant tracking, along with a greedy approach and monotonic stack to maximize the result.

How does GhostInterview help with the Create Maximum Number problem?

GhostInterview provides solutions using two-pointer techniques, explaining the greedy approach and offering feedback for optimal merging strategies.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def f(nums: List[int], k: int) -> List[int]:
            n = len(nums)
            stk = [0] * k
            top = -1
            remain = n - k
            for x in nums:
                while top >= 0 and stk[top] < x and remain > 0:
                    top -= 1
                    remain -= 1
                if top + 1 < k:
                    top += 1
                    stk[top] = x
                else:
                    remain -= 1
            return stk

        def compare(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
            if i >= len(nums1):
                return False
            if j >= len(nums2):
                return True
            if nums1[i] > nums2[j]:
                return True
            if nums1[i] < nums2[j]:
                return False
            return compare(nums1, nums2, i + 1, j + 1)

        def merge(nums1: List[int], nums2: List[int]) -> List[int]:
            m, n = len(nums1), len(nums2)
            i = j = 0
            ans = [0] * (m + n)
            for k in range(m + n):
                if compare(nums1, nums2, i, j):
                    ans[k] = nums1[i]
                    i += 1
                else:
                    ans[k] = nums2[j]
                    j += 1
            return ans

        m, n = len(nums1), len(nums2)
        l, r = max(0, k - n), min(k, m)
        ans = [0] * k
        for x in range(l, r + 1):
            arr1 = f(nums1, x)
            arr2 = f(nums2, k - x)
            arr = merge(arr1, arr2)
            if ans < arr:
                ans = arr
        return ans

Continue Practicing

#581 shortest unsorted continuous subarray #42 trapping rain water #768 max chunks to make sorted ii