IPO: Greedy Selection with Two Heaps

IPO (LeetCode 502) is a hard problem that looks intimidating at first, but the core idea is one of the cleanest greedy patterns you will encounter. You are given a set of projects, each with a capital requirement and a profit. Starting with limited capital, you want to pick projects strategically to maximize your wealth. The trick is combining a sorted order with a max-heap so that you always grab the most profitable project you can afford.

The problem

You are given k (the maximum number of projects you can complete), w (your initial capital), and two arrays: profits[i] is the profit from project i, and capital[i] is the minimum capital needed to start project i. After completing a project, your capital increases by its profit. You want to maximize your final capital after completing at most k projects.

Example: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]

With w = 0, the only affordable project is the one requiring capital 0 (profit = 1). After completing it, your capital becomes 1. Now both remaining projects are affordable (both require capital <= 1). Pick the one with profit 3. Final capital: 0 + 1 + 3 = 4.

The brute force

The naive approach: for each of your k picks, scan all n projects, find the affordable ones, and pick the one with the highest profit. Mark it as used, update your capital, and repeat.

This works but runs in O(k * n) time. When both k and n are large (up to 10^5), that can be too slow. You are also doing redundant work because projects that become affordable at one capital level stay affordable at any higher level. You should not have to re-scan them.

The key insight

Split the work into two parts with two data structures:

1. Sort projects by capital requirement. This lets you efficiently discover which projects become newly affordable as your capital grows. You walk through the sorted list with a pointer, and each project gets processed at most once.

2. Use a max-heap to track affordable projects by profit. Whenever your capital increases, push all newly affordable projects onto the max-heap. Then pop the top to get the most profitable option.

Why is this greedy choice correct? Because profit is purely additive. Completing a project with profit p increases your capital by exactly p, regardless of order. So at each step, picking the highest-profit affordable project gives you the most capital for future steps. There is no trade-off to consider, no case where picking a lower-profit project now leads to a better outcome later. The greedy choice is always optimal.

Step-by-step walkthrough

Let's trace through k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1].

Notice how the greedy approach never needs to look back. Once a project is pushed onto the max-heap, it stays there until selected. The pointer into the sorted list only moves forward. Each project is touched exactly once for the push, and at most once for the pop.

The code

import heapq

def find_maximized_capital(k: int, w: int, profits: list[int], capital: list[int]) -> int:
    n = len(profits)
    projects = sorted(zip(capital, profits))
    max_heap = []
    i = 0

    for _ in range(k):
        while i < n and projects[i][0] <= w:
            heapq.heappush(max_heap, -projects[i][1])
            i += 1

        if not max_heap:
            break

        w += -heapq.heappop(max_heap)

    return w

We sort projects by capital requirement. Then for each of the k rounds, we push all newly affordable projects onto a max-heap (using negation since Python's heapq is a min-heap). We pop the top (highest profit) and add it to w. If the heap is empty, no affordable projects remain and we stop early.

The while loop with pointer i is the key efficiency trick. Since projects are sorted by capital, we only advance i forward. Projects that were already pushed in a previous round stay in the heap. No re-scanning.

Complexity analysis

Time for the two-heap approach: Sorting is O(n log n). Each project is pushed onto and popped from the heap at most once, each operation O(log n). The total across all k rounds is O(n log n). Even if k is large, we do at most n pushes and n pops total.

Space: O(n) for the sorted array and the heap.

Building blocks

The reusable pattern here is greedy selection with a priority queue: you have a pool of items, some constraint that determines which items are currently available, and you want to pick the best available item at each step.

This same structure appears in problems like:

• Meeting Rooms II (sorted by start time, min-heap of end times to track room availability)
• Task Scheduler (greedy frequency counting to minimize idle time)
• Find K Pairs with Smallest Sums (heap to track the next best pair to consider)
• Merge K Sorted Lists (min-heap to always extend the smallest element)

The template is: sort by the constraint dimension, maintain a heap on the objective dimension, and greedily pick the top of the heap at each step. If you internalize this pattern, many hard problems reduce to "figure out what to sort by and what to heap on."

Edge cases

• No affordable projects at the start. If no project has capital[i] <= w, the max-heap is empty on the first round and you return w unchanged.
• k larger than n. You can complete at most n projects regardless of k. The code handles this naturally because the heap runs out of elements.
• All projects have capital requirement 0. Every project is affordable immediately. You just pick the top k profits. The sorted order does not matter since all capital values are the same.
• Single project. If n = 1 and k >= 1, you either can afford it or you cannot. One comparison.
• Duplicate capital requirements. Multiple projects sharing the same capital requirement all get pushed in the same inner loop iteration. The max-heap correctly surfaces the best one.

From understanding to recall

The algorithm is clean, but the details matter when you are writing it from scratch. Which structure is the max-heap and which is the sorted list? Do you sort by capital or by profit? Is the inner while condition <= or <?

The mental model that makes it stick: "sort by cost, heap by reward." You walk through projects in order of cheapness, dumping them into a reward heap. Each round, you grab the highest reward you have unlocked so far. That narrative maps directly to the code.

Spaced repetition locks it in. Write the solution from scratch, verify it, then do it again in a few days. After a few reps at increasing intervals, the sort-then-heap pattern becomes automatic and the implementation details stop tripping you up.

Related posts

• Task Scheduler - another greedy problem with scheduling
• Meeting Rooms II - heap-based scheduling
• Find K Pairs with Smallest Sums - heap-based selection

CodeBricks uses spaced repetition to help you drill patterns like this until they are second nature. Instead of re-reading solutions, you rebuild them from scratch at increasing intervals, so the pattern sticks when it matters most.