136ms python solution (beats 100%)


  • 0
    S

    Cannot avoid TLE initially. Then I read several posts from here and added some optimization. It happens that the program is very fast. So...I would like to share it but I do not claim any credit...

    from copy import copy
    from collections import defaultdict
    class Solution(object):
        def pre_process(self, num):
            l = len(num)
            summary = [[] for _ in range(l)]
            last = [l] * 10
            for i in range(l - 1, -1, -1):
                last[num[i]] = i
                summary[i] = copy(last)
            return summary
    
        def get_next(self, summary, start, end):
            for i in range(9, -1, -1):
                if summary[start][i] < end:
                    return summary[start][i], i
    
        def maxNumber(self, nums1, nums2, k):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :type k: int
            :rtype: List[int]
            """
            if len(nums1) > len(nums2):
                nums1, nums2 = nums2, nums1
            summary1 = self.pre_process(nums1)
            summary2 = self.pre_process(nums2)
            candidates = {0:0}
            max_val = []
            l1 = len(nums1)
            l2 = len(nums2)
            for i in range(k):
                print(max_val)
                updated_candidates = defaultdict(lambda: (l2, 0))
                round_max = -1
                for x, y in candidates.items():
                    remain = max(0, (k - i) - (l2 - y) - 1)
                    if l1 - x >= remain and l1 - x > 0:
                        if x + 1 == l1 - remain:
                            pos1, max1 = x, nums1[x]
                        else:
                            pos1, max1 = self.get_next(summary1, x, l1 - remain)
                    else:
                        pos1, max1 = l1, -1
                    remain = max(0, (k - i) - (l1 - x) - 1)
                    if l2 - y >= remain and l2 - y > 0:
                        if y + 1 == l2 - remain:
                            pos2, max2 = y, nums2[y]
                        else:
                            pos2, max2 = self.get_next(summary2, y, l2 - remain)
                    else:
                        pos2, max2 = l2, -1
                    round_max = max(max1, max2, round_max)
                    if max1 == round_max:
                        updated_candidates[pos1 + 1] = (y, max1)
                    if max2 == round_max:
                        updated_candidates[x] = (pos2 + 1, max2)
                max_val.append(round_max)
                candidates.clear()
                for l, v in updated_candidates.items():
                    if v[1] == round_max:
                        candidates[l] = v[0]
            return max_val

  • 0
    S

    Major optimization is when there is only one choice, do not loop from 0 till 9 and related checks.
    if x + 1 == l1 - remain:
    pos1, max1 = x, nums1[x]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.