Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
You can do at most k projects; each needs capital[i] to start and pays profits[i] on completion, which adds to your capital. Greedily, on each of the k turns, unlock every project you can now afford (capital ≤ current w) into a max-heap keyed by profit, then take the single most profitable one. Sort projects by capital so unlocking is a forward sweep; a max-heap gives the best affordable profit in O(log n). Total O(n log n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise a greedy with a moving-eligibility frontier and prove the exchange argument, instead of reaching for DP. Then whether you combine sorting (for the gate) with a heap (for the value) cleanly.
Where candidates slip
Heaping on capital instead of profit, re-scanning all projects every turn (O(nk) or worse), or re-pushing already-unlocked projects on each turn instead of using a persistent pointer.
How to stand out
State the exchange argument out loud: 'capital is monotonic non-decreasing, so any project I can afford now I can still afford later — taking the max-profit affordable one first never blocks a better choice.' Then note the two-key split.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSort projects by capital ascendingTurns left? (did < k)NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Rescan for Best Affordable Each Turn
1Hint 1Explore hintHide hint
Capital only grows. So once you can afford a project you can always afford it. Does that suggest you should ever 'save' a cheap project for later?
2Hint 2Explore hintHide hint
On each of the k turns, what single project should you do? The most profitable one you can currently afford — doing it can only raise your capital and unlock more.
3Hint 3Explore hintHide hint
Implement that literally: each turn, scan all not-yet-done projects, pick the affordable one with max profit, mark it done, add its profit. Repeat k times.
A · Core idea
The core realisation is that this is a greedy problem, not a DP one. Why? Because your capital is monotonically non-decreasing — every completed project has profit ≥ 0, so finishing it never reduces what you can afford next. That single fact powers an exchange argument: any project affordable on this turn remains affordable on every future turn, so there is never a reason to skip the most profitable affordable project in favour of a cheaper one. Taking the richest affordable project each turn is locally optimal and never blocks a globally better choice later.
Why 'most profitable affordable' and not 'cheapest' or 'highest profit overall'. Cheapest ignores payout — you'd waste turns on tiny profits. Highest-profit-overall ignores affordability — you might pick a project you literally cannot start. The sweet spot is the join of the two constraints: among the set you can start right now, take the one that pays the most. That maximally grows your capital this turn, which can only expand the affordable set next turn.
The brute-force mechanics. Keep a 'done' marker per project. Repeat k times: linearly scan all projects, and among those with capital[i] ≤ w and not yet done, track the index with the largest profit. If you found one, mark it done and add its profit to w; if none is affordable, stop early (no future turn can help because w is unchanged).
Why we don't ship this. The repeated full scan is the killer: O(k·n) with both up to 10⁵ is ~10¹⁰ operations. The fix is to notice we keep re-scanning the same projects to answer two questions — 'which are affordable?' and 'which affordable one is biggest?'. Sorting by capital answers the first with a one-way pointer; a max-heap answers the second in O(log n). That's the optimal approach below.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]turn 1, w=0
affordable: only project0 (cap 0, profit 1) → take it
w = 0 + 1 = 1, done = {0}4C · Code with teaching comments
Reference implementation previewpublic int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { int n = profits.length; boolean[] done = new boolean[n]; for (int t = 0; t < k; t++) { int best = -1;Explore the full codeHide the full code
D · Why it works and complexityO(k·n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Greedy is justified because capital is monotonic non-decreasing: an affordable project never becomes unaffordable, so grabbing the max-profit affordable project each turn can never strand a better option. That exchange argument is the whole problem.
ComplexityO(k·n) time, O(n) space — k turns, each scanning up to n projects to find the best affordable one = O(k·n). With k, n up to 10⁵ that's 10¹⁰ — too slow, but it makes the greedy correct and obvious.
E · Edge cases and pitfalls5k = 1, w = 2, profits = [5], capital = [5] — First scan finds nothing affordable (need 5, have 2) → best stays -1 → break → return 2.Explore edge casesHide edge cases
Edge cases handled
k = 1, w = 2, profits = [5], capital = [5]First scan finds nothing affordable (need 5, have 2) → best stays -1 → break → return 2.k = 10, n = 3 affordable chainOnly n projects exist; after 3 turns everything is done, later turns find best == -1 and break. 'At most k' is respected.
Pitfalls
- Forgetting the `done` marker — you'd redo the same project and overcount profit.
- Not breaking when nothing is affordable — wastes turns and (harmlessly) loops, but signals you missed the monotonicity argument.
- Picking the cheapest or globally-richest project instead of the richest *affordable* one.
Approach 2 of 2 · Optimal
Sort by Capital + Max-Heap of Affordable Profits (Optimal)
1Hint 1Explore hintHide hint
You keep re-scanning to answer two questions: which projects are affordable, and which affordable one has the max profit. Can you make each answer cheap?
2Hint 2Explore hintHide hint
Sort projects by capital ascending. Then 'newly affordable as w grows' is just advancing a pointer forward — you never look back.
3Hint 3Explore hintHide hint
Push the profits of all newly-affordable projects into a max-heap. Each turn, pop the top (best affordable profit) and add it to w. Do this up to k times, breaking if the heap empties.
A · Core idea
The brute force wasted time re-discovering the same facts. The optimal version pre-arranges the data so each fact is cheap to maintain.
Sorting by capital turns affordability into a moving frontier. After sorting projects ascending by required capital, the set of affordable projects for a given w is always a prefix of the sorted array. As w grows, that prefix only extends rightward. So we keep a single pointer idx: each turn we advance it past every project whose capital is now ≤ w, pushing those projects' profits into a max-heap. Crucially, idx is persistent across turns — a project unlocked on turn 2 stays in the heap (unconsumed) and is still a candidate on turn 5. Each project is pushed at most once over the entire run, which is why the unlock work is O(n) total, not O(n) per turn.
The max-heap answers 'best affordable profit' in O(log n). Once affordable profits live in a max-heap, the richest affordable project is the heap's top. Pop it, add it to w, and we've completed one optimal turn. We do this up to k times. If the heap is ever empty when we want to pick, nothing is affordable and — because w did not change — nothing ever will be, so we break. That early break is what makes 'at most k' correct even when fewer than k projects are reachable.
Why the heap is keyed on profit, not capital. Capital's only role is the eligibility gate, and sorting already handles that. The decision within the affordable set is purely about payout, so profit is the heap key. Mixing these up — heaping on capital — is the classic bug: you'd repeatedly start the cheapest affordable project and leave fat profits on the table.
In Python, simulate a max-heap by negating. heapq is a min-heap, so push -profit and negate on pop. Java's PriorityQueue takes Collections.reverseOrder() for a max-heap directly. Both express the same idea: O(log n) access to the largest affordable profit.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]Interactive diagram
Sorted frontier + heap interplay
turn 1, w=0Sorting makes affordability a prefix; the pointer only advances, and the heap ranks what's been unlocked.
4C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Two competing keys, two data structures: sort handles the gate (capital, a one-way frontier), the heap handles the value (profit, dynamically growing candidate set). Recognising that a problem has a monotone eligibility key and a separate ranking key is the trigger for this 'sort one, heap the other' template.
ComplexityO(n log n) time, O(n) space — Sorting is O(n log n). Across all k turns the pointer advances at most n times total (each project pushed once), and each heap push/pop is O(log n) → O(n log n) for heap ops. Overall O(n log n). Heap holds up to n profits → O(n) space.
E · Edge cases and pitfalls7k = 1, w = 2, profits = [5], capital = [5] — idx can't advance (5 > 2), heap stays empty, break on turn 1 → return 2.Explore edge casesHide edge cases
Edge cases handled
k = 1, w = 2, profits = [5], capital = [5]idx can't advance (5 > 2), heap stays empty, break on turn 1 → return 2.k larger than affordable chain lengthOnce heap empties (no project affordable with current w), we break — total picks may be < k, which is allowed.All capital = 0Turn 1 unlocks every project into the heap; subsequent turns just pop the next-largest profits — effectively pick the top-k profits.
Pitfalls
- Heaping on capital instead of profit — repeatedly starts the cheapest, not the richest, affordable project.
- Resetting the pointer `idx` each turn (re-pushing duplicates) — blows up time and double-counts.
- Forgetting the empty-heap break — in some languages this throws on poll/pop from an empty heap.
- Sorting profits and capital independently — destroys the pairing between a project's cost and its payout.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { int n = profits.length; int[][] projects = new int[n][2]; for (int i = 0; i < n; i++) { projects[i][0] = capital[i];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Heaping on capital instead of profit
The gate is capital; the choice is profit. If the heap is ordered by capital you keep starting the cheapest affordable project and leave the biggest profits unrealised.
Explore the code comparisonHide the code comparison
Heaping on capital instead of profit
The gate is capital; the choice is profit. If the heap is ordered by capital you keep starting the cheapest affordable project and leave the biggest profits unrealised.
Don't write this
for idx in range(n):
if projects[idx][0] <= w:
heapq.heappush(heap, projects[idx][0]) # capital!
w += -heapq.heappop(heap)Write this instead
while idx < n and projects[idx][0] <= w:
heapq.heappush(max_heap, -projects[idx][1]) # profit
idx += 1
w += -heapq.heappop(max_heap)2Resetting the pointer every turn
Re-scanning from 0 each turn re-pushes already-unlocked projects, double-counting them and turning the unlock cost into O(n) per turn.
Explore the code comparisonHide the code comparison
Resetting the pointer every turn
Re-scanning from 0 each turn re-pushes already-unlocked projects, double-counting them and turning the unlock cost into O(n) per turn.
Don't write this
for (int t = 0; t < k; t++) {
int idx = 0; // reset each turn -- BUG
while (idx < n && projects[idx][0] <= w) {
maxHeap.offer(projects[idx][1]);
idx++;
}
...
}Write this instead
int idx = 0; // persistent across all turns
for (int t = 0; t < k; t++) {
while (idx < n && projects[idx][0] <= w) {
maxHeap.offer(projects[idx][1]);
idx++;
}
...
}3Polling an empty heap
When nothing is affordable the heap is empty; polling it returns null (Java) or throws (Python). You must break first.
Explore the code comparisonHide the code comparison
Polling an empty heap
When nothing is affordable the heap is empty; polling it returns null (Java) or throws (Python). You must break first.
Don't write this
for (int t = 0; t < k; t++) {
while (idx < n && projects[idx][0] <= w) { maxHeap.offer(projects[idx][1]); idx++; }
w += maxHeap.poll(); // NPE if heap is empty
}Write this instead
for (int t = 0; t < k; t++) {
while (idx < n && projects[idx][0] <= w) { maxHeap.offer(projects[idx][1]); idx++; }
if (maxHeap.isEmpty()) break;
w += maxHeap.poll();
}Revise
Carry the pattern into the interview
Pattern to remember
Sort by capital + max-heap of affordable profits (greedy)
Code pattern to memorize
sort projects by capital ascending
for _ in range(k):
while next project's capital <= w: push its profit into max-heap
if heap empty: break # nothing affordable, stop
w += heap.pop_max() # take the richest affordable projectRules to remember
- 1Sort projects by capital ascending so 'what can I afford?' is a one-way moving pointer — never re-scan.
- 2The heap is keyed by profit, not capital — among everything you can afford, you always want the biggest payout.
- 3Greedy is provably optimal here: capital only ever grows, so a project affordable now stays affordable; grabbing the max profit each turn never closes a door.
- 4Use a persistent pointer into the sorted array across all k turns — affordable projects stay in the heap until chosen.
- 5Break early when the heap is empty: if nothing is affordable, no future turn helps either (w didn't change).
- 6In Python, negate profits to fake a max-heap on
heapq(a min-heap).
Use this pattern when
- Pick at most k items where eligibility depends on a growing resource (capital, budget, energy)
- Each pick relaxes the constraint for future picks (profit feeds back into capital)
- You repeatedly need the 'best available' among a dynamically growing candidate set
- Two competing keys: one gates eligibility (capital), one ranks desirability (profit)
Choose another pattern when
- You must do exactly all projects → no choice, just sum profits
- Capital does not feed back (eligibility set is static) → plain sort + take top-k
- Picking one project forbids others (mutual exclusion / dependency) → DP or graph, not greedy
- Profits can be negative and you may skip freely → different greedy / DP
Interview takeaway
When a selection problem has a gate that loosens as you pick (capital grows with profit), sort by the gate and keep a heap on the value. The sweep unlocks candidates monotonically; the heap always hands you the best one. This 'two-key' split — sort one key, heap the other — recurs in scheduling, meeting rooms, and dijkstra-flavored greedies.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternGreedy with a heap behind a monotone eligibility frontier. Whenever picks relax their own constraint (profit grows capital) and you must repeatedly choose the best currently-eligible option, sort by the eligibility key and run a heap on the value key. Same shape as Single-Threaded CPU, Course Schedule III, and Maximum Performance of a Team.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Single-Threaded CPUComing soonSort tasks by enqueue time, advance a pointer, min-heap on processing time — same 'sort the gate, heap the value' shape.
- Course Schedule IIIComing soonSort by deadline, max-heap of durations, evict the longest course when over budget — greedy + heap.
- Maximum Performance of a TeamComing soonSort by efficiency descending, min-heap of speeds of size k — gate on one key, heap on the other.
- Kth Largest Element in an ArrayCore heap-for-selection primitive that powers 'best so far' problems like this one.