LeetCode 321: Create maximum number — a dynamic programming approach

Leetcode •

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.
(Leetcode 321: Create Maximum Number)

Approach

Instead of applying the Monotonic stack as used in the algorithm proposed by dietpepsi, my solution uses Dynamic Programming to have better runtime. Let’s break the problem into smaller problems.

Extremely easy version #0

#0.1. Give one array of numbers, find maximum number of the array and its 1st appearance index.

Yes, I’m serious. In python, we can solve this easily as:

def max_and_index(array):
    max_value = max(array)
    index = array.index(max_value)
    return max_value, index

Okay, let’s increase the “complexness” a little bit.

#0.2. Give two arrays of numbers, find the maximum number of the two and its first appearance index.

Super easy, right? Let get back to this later.

Easy version #1

#1. Given one array of length n, create the maximum number of length k (k ≤ n).

Okay, this version is similar to what dietpepsi mentioned in his article. However, this time, we don’t use the monotonic stack but use recursion to find the maximum digit of each position on the final array from left to right based on facts:

By using these facts, we can construct a recursive algorithm as:

Python code:

def max_array(nums, k):
    if len(nums) == k:
        return nums
    max_value = max(nums[:len(nums)-k+1])
    index = nums.index(max_value)
    return [candidate] + max_array(nums[index+1:], k - 1)

In the worst case, this algorithm runs with O(n*k) (not counting list operations), which must be worse than with the mono stack approach.

Easy version #2

#2. Given two arrays of length m and n, create maximum number of length k = m+n

This time, we can apply dietpepsi’s solution (Easy version №2), I only implement his idea with Python code:

def is_greater(nums1, idx1, nums2, idx2):
    while idx1 < len(nums1) and idx2 < len(nums2) and nums1[idx1] == nums2[idx2]:
        idx1 += 1
        idx2 += 1
    return idx2 == len(nums2) or idx1 < len(nums1) and nums1[idx1] > nums2[idx2]

def merge(nums1, nums2):
    l1, l2 = len(nums1), len(nums2)
    i1, i2 = 0, 0
    ans = []
    while len(ans) < l1 + l2:
        if is_greater(nums1, i1, nums2, i2):
            ans.append(nums1[i1])
            i1 += 1
        else:
            ans.append(nums2[i2])
            i2 += 1
    return ans

Final solution

Okay, come back to the real problem. Recall problem #0.2, the real problem can be described as:

What is “selectable options”?

Before having the final solution, we must answer the question: What is the correct “selectable options”?

As shown in problem #1, for a single array, it’s n-k+1. For 2 arrays, we can choose up to n1+n2-k+1 numbers from each array.

Why? For a short answer, because for each round, only one array is chosen, therefore, if the max lays at (n1+n2-k)-th of the array, we can fill the rest with the leftover of that array plus all of the other array.

Simple pseudocode

max_number(nums1, nums2, k):
  option_count = len(nums1) + len(nums2) - k + 1
  
  if option_count == 1:
    -> merge(nums1, nums2, k)
  candidate1, index1 = max_and_index(nums1[:option_count])
  candidate2, index2 = max_and_index(nums2[:option_count])

  if candidate1 > candidate2:
    -> [candidate1] + max_number(nums1[index1+1:], nums2, k-1)
  else if candidate2 > candidate1:
    -> [candidate2] + max_number(nums1, nums2[index2+1:], k-1)
  else:
    -> Let's talk about this

When the two candidates are equals, it’s harder because we need to check both options to find out which branch will produce the correct answer and it’s double every time we face the equal numbers.

else:
  try1 = max_number(nums1[index1+1:], nums2, k-1)
  try2 = max_number(nums1, nums2[index2+1:], k-1)
  if try1 > try2:
    -> [candidate1] + try1
  else:
    -> [candidate2] + try2

Improvement

Denote a, b, c, d are the maximum numbers of each round on both arrays:

#1: --a-------b----c----d--->
#2: -a-----b---c-----d------>

When we run both checks to select a, we are likely to meet the checks for b, c, and d on smaller runs. This is the chance to apply dynamic programming to improve the runtime. On each run, we store the maximum value found for the input for later use.

The final solution with DP is not so different from the above pseudocode

dp = {}

max_number(nums1, nums2, k):
  if (nums1, nums2) in dp:
    return dp[(nums1, nums2)]

  option_count = len(nums1) + len(nums2) - k + 1

  if option_count == 1:
    -> merge(nums1, nums2, k)

  candidate1, index1 = max_and_index(nums1[:option_count])
  candidate2, index2 = max_and_index(nums2[:option_count])

  if candidate1 > candidate2:
    array = [candidate1] + max_number(nums1[index1+1:], nums2, k-1)
  else if candidate2 > candidate1:
    array = [candidate2] + max_number(nums1, nums2[index2+1:], k-1)
  else:
    try1 = [candidate1] + max_number(nums1[index1+1:], nums2, k-1)
    try2 = [candidate2] + max_number(nums1, nums2[index2+1:], k-1)
    array = try1 if try1 > try2 else try2

  dp[(nums1, nums2)] = ret
  return ret

Why this is fast?

Compared to the Monotonic stack approach, as pointed out in Easy version #1, recursion runs slower, but why is it faster here?

To be fair, the two algorithms run almost the same with k ~ total numbers as merge() is called most of the time. However, when k is much less than the number count, this approach jumps faster and merge() runs with smaller k.

Final code

In the solution code submitted to Leetcode, I used indexes instead of arrays for each run, therefore, it’s a little bit messive than the pseudocode. Please check out this gist for the code.

leetcode dynamic-programming python monotonic-stack