Find Subsequence of Length K With the Largest Sum — LeetCode 2099 Python Solution
EasyArrayHash TableSortingHeap (Priority Queue)
- Problem
- #2099
- Pattern
- Heap / Priority Queue
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.
Example
- Input
- nums = [2,1,3,3], k = 2
- Output
- [3,3]
- Explanation
- The subsequence has the largest sum of 3 + 3 = 6.
Python solution
Python
class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
idx = sorted(range(len(nums)), key=lambda i: nums[i])[-k:]
return [nums[i] for i in sorted(idx)]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \log n) |
| Space | O(\log n) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2099. Find Subsequence of Length K With the Largest Sum is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2099. Find Subsequence of Length K With the Largest Sum?
- LeetCode 2099. Find Subsequence of Length K With the Largest Sum is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2099. Find Subsequence of Length K With the Largest Sum?
- The Python solution on this page runs in O(n \log n).
- What is the space complexity of LeetCode 2099. Find Subsequence of Length K With the Largest Sum?
- The Python solution on this page uses O(\log n) auxiliary space.
- What topics does LeetCode 2099. Find Subsequence of Length K With the Largest Sum cover?
- LeetCode 2099. Find Subsequence of Length K With the Largest Sum is tagged Array, Hash Table, Sorting and Heap (Priority Queue) on LeetCode.