Skip to content

321. Create Maximum Number

Array Two Pointers Stack Greedy Monotonic Stack

Problem - Create Maximum Number

Hard

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.

 

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]

 

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.

Solutions

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        # def pick_largest(nums: List[int], k: int) -> List[int]:
        #     n = len(nums)
        #     stack = [0] * k
        #     top = -1
        #     remain = n - k
        #     for num in nums:
        #         while top >= 0 and stack[top] < num and remain > 0:
        #             top -= 1
        #             remain -= 1
        #         if top + 1 < k:
        #             top += 1
        #             stack[top] = num
        #         else:
        #             remain -= 1
        #     return stack

        # def compare(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
        #     if i >= len(nums1):
        #         return False
        #     elif j >= len(nums2):
        #         return True
        #     elif nums1[i] > nums2[j]:
        #         return True
        #     elif nums1[i] < nums2[j]:
        #         return False
        #     else:
        #         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
        #     result = [0] * (m + n)
        #     for k in range(m + n):
        #         if compare(nums1, nums2, i, j):
        #             result[k] = nums1[i]
        #             i += 1
        #         else:
        #             result[k] = nums2[j]
        #             j += 1
        #     return result

        # m, n = len(nums1), len(nums2)
        # left, right = max(0, k - n), min(k, m)
        # result = [0] * k
        # for val in range(left, right + 1):
        #     temp = pick_largest(nums1, val)
        #     temp2 = pick_largest(nums2, k - val)
        #     temp3 = merge(temp, temp2)
        #     if result < temp3:
        #         result = temp3

        # return result

        def pick_largest(nums: List[int], val: int) -> List[int]:
            stack = []
            drop = len(nums) - val
            for num in nums:
                while drop and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:val]

        def merge(nums1: List[int], nums2: List[int]) -> List[int]:
            result = []
            while nums1 or nums2:
                if nums1 > nums2:
                    result.append(nums1.pop(0))
                else:
                    result.append(nums2.pop(0))
            return result

        m, n = len(nums1), len(nums2)
        result = []
        for val in range(max(0, k - n), min(k, m) + 1):
            part1 = pick_largest(nums1, val)
            part2 = pick_largest(nums2, k - val)
            check = merge(part1, part2)
            result = max(result, check)
        return result

Submission Stats:

  • Runtime: 99 ms (94.66%)
  • Memory: 18 MB (60.36%)