⚡Flashcard Drill➔
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

  1. Sort the projects by required capital.
  2. At each step, push every project whose capital requirement is now affordable into a max-heap keyed by profit.
  3. Pop the most profitable project and add its profit to the capital.
  4. Repeat up to k times, 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 run k times 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems