Heap Solution with Full Explanation! 🅚 ➕ 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find the maximum subsequence of length k, the main idea is to ensure we always keep 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find the maximum subsequence of length $$k$$, the main idea is to ensure we always keep track of the $$k$$ largest elements in their original order. Using a min-heap will help us efficiently manage and retrieve these elements.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization**:\n   - Create an empty list `subsequence` to store the result.\n   - Use a min-heap `min_heap` to keep the top $$k$$ elements seen so far.\n\n2. **Processing the Elements**:\n   - Iterate through the list `nums` with both the value `num` and its index `i`.\n   - Push the tuple `(num, i)` into `min_heap`.\n   - If the size of `min_heap` exceeds $$k$$, remove the smallest element (which will be at the root of the heap).\n\n3. **Sorting and Collecting Results**:\n   - Sort the heap based on the original indices to maintain the order.\n   - Extract the values from the sorted heap and append them to `subsequence`.\n\n4. **Return the Result**:\n   - Return the `subsequence` list containing the $$k$$ largest elements in their original order.\n\n# Complexity\n- Time complexity:\n  - The overall time complexity is $$O(n \\log k)$$ because we push elements into the heap (which takes $$O(\\log k)$$ time) for each of the $$n$$ elements.\n  \n- Space complexity:\n  - The space complexity is $$O(k)$$ for storing the heap of size $$k$$.\n\n# Code\n```python\nclass Solution:\n    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n        # Min Heap\n        subsequence = []\n        min_heap = []\n\n        for i, num in enumerate(nums): \n            heapq.heappush(min_heap, (num, i))\n            if len(min_heap) > k:\n                heapq.heappop(min_heap)\n\n        min_heap.sort(key=lambda x: x[1])\n        \n        for num, _ in min_heap:\n            subsequence.append(num)\n\n        return subsequence\n\n        # O(n log k) time.\n        # O(k) space.\n```\nUPVOTE IF HELPFUL \uD83E\uDD19  \nTHANKS
['Python3']