321: Space 98.63%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Define a function called "get_max_subseq" that takes two inputs: a lis
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Define a function called "get_max_subseq" that takes two inputs: a list of integers called "nums" and an integer "k" representing the length of the subsequence we want to extract from the list.\n2. Initialize an empty stack to hold the maximum subsequence and iterate through the input list "nums" using a for loop and the enumerate() function.\n3. For each element "num" in "nums", do the following:\na. While the stack is not empty AND the length of the remaining part of "nums" (i.e., len(nums) - i) plus the length of the stack is greater than "k" AND the last element in the stack is less than "num", pop the last element from the stack.\nb. If the length of the stack is less than "k", append "num" to the stack.\n4. Return the resulting stack, which contains the maximum subsequence of "nums" of length "k".\n5. Define a function called "merge" that takes two inputs: two lists of integers called "nums1" and "nums2".\n6. Initialize an empty list called "merged" to hold the merged list.\n7. Initialize two counters i and j to 0 to track the current index of "nums1" and "nums2", respectively.\n8. While i is less than the length of "nums1" OR j is less than the length of "nums2", do the following:\na. If i is greater than or equal to the length of "nums1", append the jth element of "nums2" to "merged" and increment j by 1.\nb. Else if j is greater than or equal to the length of "nums2", append the ith element of "nums1" to "merged" and increment i by 1.\nc. Else if the remaining part of "nums1" starting from the ith index is lexicographically greater than the remaining part of "nums2" starting from the jth index, append the ith element of "nums1" to "merged" and increment i by 1.\nd. Otherwise, append the jth element of "nums2" to "merged" and increment j by 1.\n9. Return the resulting merged list.\n10. Initialize an empty list called "ans" to hold the maximum subsequence of length "k" from "nums1" and "nums2".\n11. Loop through all possible lengths "i" of the subsequence from "nums1" ranging from max(0, k - len(nums2)) to min(len(nums1), k) + 1.\n12. Calculate the corresponding subsequence of "nums2" of length "j" by subtracting "i" from "k".\n13. Call the "get_max_subseq" function on "nums1" with "i" as the input "k" and store the result in "subseq1".\n14. Call the "get_max_subseq" function on "nums2" with "j" as the input "k" and store the result in "subseq2".\n15. Call the "merge" function on "subseq1" and "subseq2" and store the result in "merged".\n16. Update "ans" to be the maximum value between the current value of "ans" and "merged" using the max() function.\n17. Return the resulting maximum subsequence of length "k" from "nums1" and "nums2", which is stored in "ans".\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n        def get_max_subseq(nums, k):\n            stack = []\n            for i, num in enumerate(nums):\n                while stack and len(nums) - i + len(stack) > k and stack[-1] < num:\n                    stack.pop()\n                if len(stack) < k:\n                    stack.append(num)\n            return stack\n        \n        def merge(nums1, nums2):\n            merged = []\n            i, j = 0, 0\n            while i < len(nums1) or j < len(nums2):\n                if i >= len(nums1):\n                    merged.append(nums2[j])\n                    j += 1\n                elif j >= len(nums2):\n                    merged.append(nums1[i])\n                    i += 1\n                elif nums1[i:] > nums2[j:]:\n                    merged.append(nums1[i])\n                    i += 1\n                else:\n                    merged.append(nums2[j])\n                    j += 1\n            return merged\n        \n        ans = []\n        for i in range(max(0, k - len(nums2)), min(len(nums1), k) + 1):\n            j = k - i\n            subseq1 = get_max_subseq(nums1, i)\n            subseq2 = get_max_subseq(nums2, j)\n            merged = merge(subseq1, subseq2)\n            ans = max(ans, merged)\n        return ans\n\n```
['Stack', 'Greedy', 'Monotonic Stack', 'Python', 'Python3']