Coding Interview PatternsIPO
HardTop K Elements

IPO

Explanation & Solution

Practice Problem

Description

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital requirement capital[i].

You have an initial capital w. When you complete a project, you earn its profit and the profit is added to your total capital.

Pick a list of at most k distinct projects to maximize your final capital, and return the final maximized capital.

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

Output: 4

Explanation: With initial capital 0, you can only start project 0 (capital requirement 0), earning profit 1. Your capital becomes 1. Now you can start project 1 or 2. Choose project 2 (profit 3) to maximize capital. Final capital = 0 + 1 + 3 = 4.

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

Approach

Top K Elements pattern

1. Pair and Sort Projects by Capital

  • Create an array of [capital, profit] pairs for each project.
  • Sort this array by capital requirement in ascending order.
  • This allows us to efficiently find all projects we can afford as our capital grows.

2. Implement a Max-Heap

  • Since JavaScript has no built-in heap, implement a MaxHeap class with push, pop, and internal _bubbleUp / _sinkDown methods.
  • The heap will store profits of affordable projects, with the largest profit always at the top.

3. Greedy Selection Loop (up to k rounds)

  • For each of the k rounds:
  • Unlock projects: Walk through the sorted projects and push all profits where capital[i] <= w into the max-heap.
  • Pick the best: Pop the maximum profit from the heap and add it to w.
  • Early exit: If the heap is empty (no affordable projects), stop early since no more progress can be made.

4. Return Final Capital

  • After completing at most k projects, w holds the maximized capital.

Key Insight

The greedy strategy works because picking the highest-profit affordable project at each step is always optimal. A lower-profit project can never unlock more options than a higher-profit one (both increase capital, but the higher profit increases it more). Sorting by capital and using a max-heap gives O(n log n) time complexity and O(n) space complexity.

Solution Code

Previous
Maximum Subsequence Score