MediumNo. 2599LeetCode Premium
Make the Prefix Sum Non-negative — LeetCode 2599 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums. You can apply the following operation any number of times: Pick any element from nums and put it at the end of nums.
Example
- Input
- nums = [2,3,-5,4]
- Output
- 0
- Explanation
- we do not need to do any operations.
Python solution
class Solution:
def makePrefSumNonNegative(self, nums: List[int]) -> int:
h = []
ans = s = 0
for x in nums:
s += x
if x < 0:
heappush(h, x)
while s < 0:
s -= heappop(h)
ans += 1
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)where n is the length of the array nums
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2599. Make the Prefix Sum Non-negative 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
| No. | Problem | Difficulty |
|---|---|---|
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 1353 | Maximum Number of Events That Can Be Attended | Medium |
| 1383 | Maximum Performance of a Team | Hard |
| 1642 | Furthest Building You Can Reach | Medium |
Frequently asked questions
- How hard is LeetCode 2599. Make the Prefix Sum Non-negative?
LeetCode 2599. Make the Prefix Sum Non-negative is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2599. Make the Prefix Sum Non-negative?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2599. Make the Prefix Sum Non-negative?
The Python solution on this page uses O(n), where n is the length of the array nums auxiliary space.
- What topics does LeetCode 2599. Make the Prefix Sum Non-negative cover?
LeetCode 2599. Make the Prefix Sum Non-negative is tagged Greedy, Array and Heap (Priority Queue) on LeetCode.
- Is LeetCode 2599. Make the Prefix Sum Non-negative a premium problem?
Yes. LeetCode 2599. Make the Prefix Sum Non-negative is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.