← DSA Atlas
Dedicated problem page · #502

IPO

HardHeap and Priority QueueGreedy with a max-heap of affordable optionsSort by cost + max-heap by profit
Solve on LeetCode ↗
502
HardHeap and Priority QueueSort by cost + max-heap by profitGreedy with a max-heap of affordable options

IPO

You start with w capital and can complete at most k distinct projects. Project i requires capital[i] to start and yields a pure profit[i] added to your capital when finished. Once a project is done its profit becomes available capital for later projects. Return the maximum capital you can hold after finishing at most k projects.

Open official problem prompt ↗
In plain English

Choose up to k projects, in some order, that leave you with the largest possible final capital, respecting that each project can only be started once you can afford its capital requirement.

Picture it like this

A venture investor with limited cash unlocks bigger deals as returns roll in. Each round they fund the most profitable deal they can currently afford; the payoff enlarges their wallet, which opens richer deals next round.

Example
Input
k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Output
4
Why
With w=0 only project 0 (cost 0) is affordable; finishing it gives w=1, unlocking projects costing 1. Take the profit-3 project for w=4.
Constraints
1 <= k <= 10^50 <= w <= 10^91 <= profits.length == capital.length <= 10^50 <= profits[i] <= 10^40 <= capital[i] <= 10^9
Pattern lesson

See the pattern, then code

Greedy with a max-heap of affordable options
Recognition clue

Repeatedly picking the best currently-affordable option as your budget grows is a classic greedy-plus-heap: sort candidates by a threshold and pull the best available from a max-heap.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. At each of the k rounds you should do the most profitable project you can currently afford, because doing it only raises your capital and never removes future options. A max-heap keyed on profit gives that best-affordable project instantly, and rising capital unlocks more projects to add.

New words, made simpleKnow these before the algorithm
Capital requirement
The minimum cash needed to start a project; profit is added on top, never subtracted.
Affordable set
All projects whose requirement is at most the current capital.
Greedy choice
Taking the locally best option (max profit affordable) trusting it leads to the global optimum here.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try all orders

Combinatorially impossible for the given sizes.

Explore every sequence of up to k projects.

Time ExponentialSpace Exponential
Rescan every round

Correct but O(k*n) is too slow when both are up to 10^5.

Each round linearly scan all projects for the best affordable one.

Time O(k*n)Space O(1)
Best choiceSort by cost + profit max-heap

Each project enters the heap once and the best affordable is O(log n) to fetch.

Sweep projects into a max-heap as capital rises and always pop the top profit.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

At the start of each round, the max-heap contains exactly the profits of every project affordable at the current capital that has not yet been chosen.

Why this is correct

Reasoning

Because profit only increases capital, picking the most profitable affordable project can never shrink the future affordable set — it can only grow it. So the greedy maximum-profit choice each round dominates any alternative, and the pointer plus heap ensures no affordable project is ever missed.

The algorithm in three movesSay these aloud before coding
1Pair each project as (capital, profit) and sort by capital ascending

w=0: affordable {(0,1)} -> heap[1]; pop 1 -> w=1

2Before each pick, push every project whose capital <= current w onto a max-heap of profits

w=1: affordable {(1,2),(1,3)} -> heap[3,2]; pop 3 -> w=4

3Pop the largest available profit and add it to w

picks used: 2 -> return 4

4Stop after k picks or when no project is affordable

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(0,1)0
(1,2)1
(1,3)2
1 · Readcapital/profit
2 · AskOrder by cost?
3 · Update stateprojects = [(0,1),(1,2),(1,3)]
4 · ResultCheapest first.
Key takeaway

Projects sorted by cost; the heap holds all currently-affordable profits.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6Pair and sort

    Sorting (capital, profit) by capital lets a single forward pointer reveal newly affordable projects as w grows.

  2. 2
    Lines 10-12Unlock affordable

    Add every project whose cost is within budget to the max-heap (profits negated for Python's min-heap).

  3. 3
    Lines 13-14Bail if stuck

    If nothing is affordable, no future round can help, so stop early.

  4. 4
    Lines 15Take best profit

    Pop the largest available profit and grow capital by it.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No project affordable at start (return w unchanged)
  • k larger than the number of projects (limited by the heap emptying)
  • All projects require 0 capital
  • Projects with equal profits or equal capital requirements
!

Common beginner mistakes

  • Re-adding projects to the heap across rounds — the pointer i must only move forward so each enters once
  • Using a min-heap and picking the smallest profit
  • Assuming you must always do exactly k projects; you stop when none are affordable
  • Sorting by profit instead of by capital, breaking the unlock order
Check your understanding

Why is greedily taking the highest-profit affordable project each round guaranteed optimal, unlike most 'pick the best now' heuristics?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word#703Kth Largest Element in a StreamFixed-size min-heap (bounded top-k)