10 lines with explanation
Gready + Merge Sort\nSince we need construct the maximum number from given arrays, the gready approach seems to be the core diea resovling this problem, which i
### Gready + Merge Sort\nSince we need construct the maximum number from given arrays, the gready approach seems to be the core diea resovling this problem, which is to select the maximum number and check if we can pick it. We can\'t pick the current number if the number of remaining elements are smaller than *K* as we don\'t have enough elements to pick *k* times. There are two different apparchs for us to select maximum elements. The first one is to find maximum between 2 arrays, namely we combine 2 arraysy and pick the maximum number to construct the global maximum result. The other one is to select maximum number for each array respectively, and merge it as local maximum and return the maximum one. As the local maximum is not always the global maximum in the first approach, we need go with second appraoch, which is much easier to implement as well.\nHence, the algorithm could be\n1. We pick the first `length` th maximum numbers from *nums1* and the other `k - length` th maximum numbers from *nums2*\n2. Construct the local maximum nubmer by merging and record it if it\'s the maximum so far\n3. Repeat the process for the `length` + 1 until it reaches the `min(k, nums1.length)`\n\nNote, we have variance on the `merge`, where we pick larger one if `nums1[i] != nums2[j]`, otherwise the one with larger successors.\n\n```python\n    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n        m = len(nums1)\n        n = len(nums2)\n        \n        def getMax(nums, k):\n            ans, i, n = [], 0, len(nums)\n            while i < n:\n                while ans and nums[i] > ans[-1] and n - i + len(ans) > k:\n                    ans.pop()\n                ans.append(nums[i]) \n                i += 1\n            return ans[:k]\n        \n        def merge(nums1, nums2):\n            return [max(nums1, nums2).popleft() for _ in range(len(nums1) + len(nums2))]\n            \n        return max(merge(deque(getMax(nums1, length)), deque(getMax(nums2, k - length))) for length in range(max(0, k - n), min(k, m) + 1))\n```\n\n*Time Complexity* = **O(k(n1 + n2)^2)**, *n1*, *n2* denotes the length of arrays respectively\n*Space Complexity* = **O(k)**
[]