Java | Priority Queue | O(N*log(K) + K*log(K)) time and O(K) space
The idea is that to get kth max sequence is using kth max elements. That can be solved similarly to this problem: https://leetcode.com/problems/kth-largest-elem
- The idea is that to get kth max sequence is using kth max elements. That can be solved similarly to this problem: https://leetcode.com/problems/kth-largest-element-in-an-array/. \n- However, we\'re not only storing the value but also the index so later, we can sort by the index later for the result. \n- Complexity for PQ is O(N log K) since we only maintain K elements in the heap \n- Complexity for sorting for the result is O(K log K) \n- Time is O(K) in the heap.\n\n```java\nclass Solution {\n    public int[] maxSubsequence(int[] nums, int k) {\n        int n = nums.length; \n        if (k == 0) return new int[0]; \n        if (k == n) return nums;\n        \n        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(pair -> pair[0])); \n        \n        for(int i = 0; i < n; i++) {\n            minHeap.add(new int[] {nums[i], i});\n            if (minHeap.size() > k) {\n                minHeap.poll();\n            }\n        }\n        \n        int[][] res = new int[k][2]; \n        for(int i = 0; i < k; i++) {\n            res[i] = minHeap.poll();\n        }\n        \n        Arrays.sort(res, Comparator.comparingInt(pair -> pair[1]));\n        return Arrays.stream(res).map(pair -> pair[0]).mapToInt(Integer::intValue).toArray();\n    }\n}\n```
['Heap (Priority Queue)', 'Java']