Compile Ready
Module 6 · Advanced Heap

IPO

HardProblem 12 of 14 10 min read ~32 min to solve LeetCode
HeapPriority QueueGreedySortingCapital Allocation
Asked atGoogleAmazonMicrosoftMetaOracle

Problem Statement

You are given an integer k, initial capital w, and two arrays profits and capital. Project i can only be started when your current capital is at least capital[i]. Once completed, it adds profits[i] to your capital. Choose at most k distinct projects to maximize your final capital.

Input

An integer k, an integer w, and equal-length arrays profits and capital describing each project's reward and capital threshold.

Output

An integer: the maximum capital reachable after selecting at most k projects.

Constraints

  • •1 <= k <= 10^5
  • •0 <= w <= 10^9
  • •1 <= profits.length <= 10^5
  • •profits.length == capital.length
  • •0 <= profits[i] <= 10^4
  • •0 <= capital[i] <= 10^9

Examples

Example 1

Input: 
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Start with the only affordable project for profit 1. Capital becomes 1, which unlocks the two remaining projects, then choose profit 3 for final capital 4.

Example 2

Input: 
k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6
Explanation: Choose profit 1, then profit 2, then profit 3 as each new capital level unlocks the next project.

Example 3

Input: 
k = 1, w = 2, profits = [1,2,3], capital = [1,1,2]
Output: 5
Explanation: All projects are affordable at capital 2, so the best single choice is the project with profit 3.

Learning Objectives

  • Recognise the expanding-affordable-set pattern where each greedy choice can unlock more candidates.
  • Sort projects by required capital and use a pointer to reveal all projects affordable at the current capital.
  • Use a max-heap to choose the highest profit among currently affordable projects.
  • Explain why taking the maximum affordable profit is safe because more capital never reduces future options.

Intuition

Pattern recognition starts with the phrase currently affordable. The candidates are not all available at the same time; each completed project increases capital and may unlock more projects. That is the signal for sorting by the unlock threshold and using a heap for the best choice inside the current frontier.

The greedy invariant is: before each project selection, the max-heap contains exactly the profits of every unchosen project whose capital requirement is at most current capital. Among those projects, choosing the largest profit is always safe because it produces capital at least as high as any smaller choice. Higher capital can only unlock more future projects; it never locks a project again.

The trap is sorting by profit once and scanning from the top. A high-profit project may be locked now, and repeatedly checking locked projects wastes time. Sorting by capital handles discovery, while the max-heap handles selection.

Common mistakes

  • ×Choosing the lowest capital requirement project instead of the highest profit among affordable projects.
  • ×Pushing every project into the profit heap before verifying that it is affordable.
  • ×Forgetting to stop early when the profit heap is empty before all **k** selections are used.
  • ×Sorting by profit only, which mixes locked and affordable projects and loses the efficient frontier.

Algorithm Explanation

Key idea

Sort projects by required capital. Sweep a pointer through that sorted list and move every newly affordable project into a max-heap of profits. Each of up to k rounds first unlocks everything affordable at the current capital, then chooses the largest profit from the heap.

The informal correctness argument is an exchange argument. At any round, locked projects are impossible to choose. If an optimal plan chooses an affordable project with profit p while another affordable project has profit q >= p, swapping the first choice to q leaves capital at least as large after the round. Every later project that was affordable in the original plan is still affordable, and possibly more are unlocked. Repeating that swap yields an optimal plan that always takes the maximum affordable profit.

Heap walkthrough

For k = 2, w = 0, profits = [1,2,3], and capital = [0,1,1], the projects sorted by capital are profit 1 at capital 0, profit 2 at capital 1, and profit 3 at capital 1. Start with capital 0 and an empty max-heap. Round 1 unlocks profit 1, so the heap is [1]; polling it raises capital to 1. Round 2 now unlocks profits 2 and 3, so the heap becomes [3,2]; polling 3 raises capital to 4. The running capital always follows the best available profit choice.

Algorithm

  1. Build project pairs [capital requirement, profit] and sort them by capital requirement.
  2. Keep a pointer to the first not-yet-unlocked project and a max-heap of affordable profits.
  3. Repeat at most k times.
  4. While the pointer project requires capital at most the current capital, push its profit into the max-heap and advance the pointer.
  5. If the max-heap is empty, stop because no project can currently be started.
  6. Poll the maximum profit and add it to current capital.
  7. Return the final capital.

Solutions

Solution: Capital-sorted scan with max-profit heap

When to prefer this:

Use this whenever projects have a prerequisite threshold and completing one candidate increases the resource that unlocks future candidates.

Sort projects by required capital so affordability is discovered in one forward scan. The max-heap stores only profits of projects that are currently affordable and not yet chosen. For each project slot, unlock all affordable projects, take the largest profit, and add it to capital.

Step-by-step

  1. Create projects as pairs of required capital and profit.
  2. Sort projects by required capital in ascending order.
  3. Maintain nextProject as the first locked project not yet processed.
  4. Before each choice, move every project with requirement at most currentCapital into affordableProfits.
  5. If no affordable profit exists, break early.
  6. Poll the maximum profit and add it to currentCapital.
  7. Return currentCapital after at most k selections.
Time

O((n + k) log n)

Space

O(n)

Sorting costs O(n log n); each project enters the heap once, and at most k projects are polled.

Java implementation

Loading…

Dry Run

Sample input

k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]. Projects sorted by capital are [0,1], [1,2], [1,3].

roundcapital before unlocknewly affordable profitsmax-heap before pickpicked profitcapital after pick
10[1][1]11
21[2,3][3,2]34

After the first project, capital 1 unlocks both remaining projects. The max-heap chooses profit 3, so the final capital is 4 after two selections.

Interview Tips

Separate the two responsibilities clearly: sorting by capital discovers what is affordable, while the max-heap chooses the best profit from the affordable set. The proof should mention monotonic capital: choosing more profit now cannot make future feasibility worse.

Likely follow-ups

  • How would you return the selected project indices in order?
  • What changes if profits can be negative and you may choose fewer than **k** projects?
  • How would the solution change if capital is spent when a project starts instead of only required as a threshold?
  • Could you solve it with two heaps instead of sorting, and what tradeoff would that have?

Similar Problems

Furthest Building You Can Reach
MediumAlso uses a heap to make the best choice as resources evolve.
Minimum Cost to Hire K Workers
HardAnother advanced greedy problem where sorting defines the frontier and a heap optimizes inside it.
Task Scheduler
MediumRepeatedly chooses the best currently available task using heap priority.
Kth Largest Element in an Array
MediumPractices choosing the right heap direction for top candidates.
Maximum Performance of a Team
HardCombines sorting by a limiting ratio with a heap-maintained candidate set.

Key Takeaways

  • Sort by the prerequisite threshold, not by the reward.
  • The max-heap must contain only currently affordable projects.
  • Maximum affordable profit is safe because more capital can only help future unlocks.
  • Stop early when no affordable project exists, even if unused selections remain.
Reusable template: Expanding-frontier greedy: sort by the unlock threshold, push newly feasible candidates into a priority queue, and repeatedly choose the best payoff among feasible candidates.