NeetCode #551LC-502HardHeap / Priority QueueNC 250
← Back to All Problems#551 · #502 · IPO(IPO)
📌 Problem Statement & Constraints
You have
k initial capital w and n projects with profits[i] and capital[i]. You may start at most k projects, each requiring the available capital. Return the maximum final capital. Constraints: 1 <= k <= 10^5, 1 <= w <= 10^9, n <= 10^5.💡 Core Algorithmic Approaches
- Sort the projects by required capital.
- At each step, push every project whose capital requirement is now affordable into a max-heap keyed by profit.
- Pop the most profitable project and add its profit to the capital.
- Repeat up to
ktimes, or until no affordable project remains.
💻 Benchmark Python3 Implementation
class Solution:
def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
import heapq
n = len(profits)
projects = sorted(zip(capital, profits))
h = [] # max-heap of profits (negated)
i = 0
for _ in range(k):
# unlock every project that is now affordable
while i < n and projects[i][0] <= w:
heapq.heappush(h, -projects[i][1])
i += 1
if not h:
break # nothing affordable -> stop
w += -heapq.heappop(h) # take the most profitable
return w⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n + k log n): the sort plus at most n pushes and k pops.
💾 Space Complexity
O(n) for the heap.
⚠️ Interview Pitfalls & Follow-ups
- Re-scanning all projects at each step: O(n * k). The sorted array plus a single pointer makes each project considered once.
- Taking the project with the smallest capital requirement: the objective is to maximise capital, so profit drives the choice.
- Forgetting the
if not h: break: the loop would runktimes doing nothing. - Using a min-heap: the most profitable project must come first.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.