HardNo. 2386
Find the K-Sum of an Array — LeetCode 2386 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Sorting, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an integer array nums and a positive integer k. You can choose any subsequence of the array and sum all of its elements together.
Example
- Input
- nums = [2,4,-2], k = 5
- Output
- 2
- Explanation
- All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
Python solution
class Solution:
def kSum(self, nums: List[int], k: int) -> int:
mx = 0
for i, x in enumerate(nums):
if x > 0:
mx += x
else:
nums[i] = -x
nums.sort()
h = [(0, 0)]
for _ in range(k - 1):
s, i = heappop(h)
if i < len(nums):
heappush(h, (s + nums[i], i + 1))
if i:
heappush(h, (s + nums[i] - nums[i - 1], i + 1))
return mx - h[0][0]Complexity
- Time
- O(n × log n + k × log k), where n is the length of the array nums
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2386. Find the K-Sum of an Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0506 | Relative Ranks | Easy |
| 0912 | Sort an Array | Medium |
| 0973 | K Closest Points to Origin | Medium |
| 1094 | Car Pooling | Medium |
Frequently asked questions
- How hard is LeetCode 2386. Find the K-Sum of an Array?
LeetCode 2386. Find the K-Sum of an Array is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2386. Find the K-Sum of an Array?
The Python solution on this page runs in O(n × log n + k × log k), where n is the length of the array \textit{nums}.
- What is the space complexity of LeetCode 2386. Find the K-Sum of an Array?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2386. Find the K-Sum of an Array cover?
LeetCode 2386. Find the K-Sum of an Array is tagged Array, Sorting and Heap (Priority Queue) on LeetCode.