LeetCode 502: IPO

Problem Restatement

We are given n projects.

Each project has:

We start with capital w.

We can finish at most k distinct projects.

After finishing a project, its profit is added to our capital.

We need to return the maximum final capital possible after choosing at most k projects.

The problem asks us to maximize total capital after doing up to k projects, where each project requires some starting capital and gives profit after completion. The final answer fits in a 32-bit signed integer.

Input and Output

Function shape:

class Solution:
    def findMaximizedCapital(
        self,
        k: int,
        w: int,
        profits: List[int],
        capital: List[int],
    ) -> int:
        ...

Examples

Example 1:

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

At the start, we have capital 0.

Only projects with required capital <= 0 are available.

So we can choose project 0:

capital = 0 + 1 = 1

Now projects with required capital 1 are available.

We should choose the most profitable available project, profit 3:

capital = 1 + 3 = 4

Then choose profit 2:

capital = 4 + 2 = 6

The answer is:

6

Example 2:

k = 1
w = 2
profits = [1, 2, 3]
capital = [1, 1, 2]

All projects are affordable because their required capital is at most 2.

We can choose only one project.

So we choose the project with profit 3.

The answer is:

5

First Thought: Try All Project Orders

A direct approach is to try every possible sequence of projects.

At each step, choose one affordable unused project.

Then update capital and continue.

This explores many possible project orders.

For n projects and up to k choices, this can become very large.

Even when k is small, the branching factor can be high.

Problem With Brute Force

The brute force method wastes time comparing many sequences that do not need to be compared.

At any point, if several projects are affordable, choosing the one with the highest profit is always best.

A higher profit immediately increases capital more.

More capital can only make more projects affordable, never fewer.

So we do not need to explore all affordable choices.

We should greedily choose the best profit among currently affordable projects.

Key Insight

The problem has two requirements:

1. We need to know which projects are affordable with current capital.
2. Among affordable projects, we need to choose the largest profit.

Use two structures:

Python has a min heap, so we store negative profits to simulate a max heap.

Algorithm

Create project pairs:

projects = sorted(zip(capital, profits))

Each pair is:

(required_capital, profit)

Use an index i to scan projects sorted by required capital.

Use a heap available to store profits of projects we can currently afford.

For each of up to k rounds:

1. Move every project with required_capital <= w into the heap.
2. If the heap is empty, no project can be started, so stop.
3. Pop the largest profit from the heap.
4. Add that profit to w.

After the loop, return w.

Correctness

At every step, the algorithm adds all projects whose required capital is at most the current capital w into the heap.

Therefore, the heap contains exactly the projects that are currently affordable and have not already been chosen.

The algorithm then chooses the affordable project with the largest profit.

This greedy choice is safe because choosing a larger profit gives capital at least as large as choosing any other affordable project. Since project availability depends only on current capital, having more capital cannot remove future options.

So after each chosen project, the greedy algorithm has capital at least as large as any alternative strategy that chose the same number of projects.

By repeating this argument for up to k projects, the algorithm produces the maximum possible final capital.

Complexity

Since each project is pushed into the heap at most once and popped at most once, this is often written as:

O(n log n + k log n)

or simply:

O((n + k) log n)

Implementation

from typing import List
import heapq

class Solution:
    def findMaximizedCapital(
        self,
        k: int,
        w: int,
        profits: List[int],
        capital: List[int],
    ) -> int:
        projects = sorted(zip(capital, profits))
        available = []

        i = 0
        n = len(projects)

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

            if not available:
                break

            w += -heapq.heappop(available)

        return w

Code Explanation

We combine the two arrays into project pairs:

projects = sorted(zip(capital, profits))

Sorting by capital lets us move affordable projects into the heap in one pass.

The heap stores profits of projects that are currently available:

available = []

Python’s heapq is a min heap.

To get max heap behavior, we push negative profits:

heapq.heappush(available, -profit)

The pointer i tracks the next project not yet considered:

i = 0

For each project selection round:

for _ in range(k):

we move all newly affordable projects into the heap:

while i < n and projects[i][0] <= w:

If no project is available, we cannot continue:

if not available:
    break

Otherwise, choose the largest available profit:

w += -heapq.heappop(available)

The negative sign converts it back to a positive profit.

Finally, return the final capital:

return w

Testing

def test_find_maximized_capital():
    s = Solution()

    assert s.findMaximizedCapital(
        2,
        0,
        [1, 2, 3],
        [0, 1, 1],
    ) == 4

    assert s.findMaximizedCapital(
        3,
        0,
        [1, 2, 3],
        [0, 1, 1],
    ) == 6

    assert s.findMaximizedCapital(
        1,
        2,
        [1, 2, 3],
        [1, 1, 2],
    ) == 5

    assert s.findMaximizedCapital(
        3,
        0,
        [1, 2, 3],
        [1, 1, 2],
    ) == 0

    assert s.findMaximizedCapital(
        4,
        2,
        [2, 3, 1, 5, 3],
        [4, 4, 2, 3, 3],
    ) == 14

    print("all tests passed")

Test meaning: