Leetcode 321: https://leetcode.com/problems/create-maximum-number/

leetcode_321_create_maximum_number.py

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


def find_max_index(nums, start, end):
    if start >= end or start >= len(nums):
        return -1
    max_index = start
    for i in range(start + 1, min(len(nums), end)):
        if nums[i] > nums[max_index]:
            max_index = i

    return max_index


def sol(nums1, nums2, k):
    dp = {}
    l1, l2 = len(nums1), len(nums2)
    l = l1 + l2

    def rec(i1, i2, n):
        if (i1, i2) in dp:
            return dp[(i1, i2)]
        if n == 0:
            return []

        max_searchable_length = l - i1 - i2 + 1 - n
        if max_searchable_length == 1:
            return merge(nums1[i1:], nums2[i2:])

        candidate_index_1 = find_max_index(nums1, i1, i1 + max_searchable_length)
        candidate_index_2 = find_max_index(nums2, i2, i2 + max_searchable_length)
        candidate_1 = nums1[candidate_index_1] if candidate_index_1 >= 0 else -1
        candidate_2 = nums2[candidate_index_2] if candidate_index_2 >= 0 else -1

        if candidate_1 > candidate_2:
            ret = [candidate_1] + rec(candidate_index_1 + 1, i2, n - 1)
        elif candidate_2 > candidate_1:
            ret = [candidate_2] + rec(i1, candidate_index_2 + 1, n - 1)
        else:
            try1 = rec(candidate_index_1 + 1, i2, n - 1)
            try2 = rec(i1, candidate_index_2 + 1, n - 1)
            if try1 > try2:
                ret = [candidate_1] + try1
            else:
                ret = [candidate_2] + try2
        dp[(i1, i2)] = ret
        return ret

    return rec(0, 0, k)