LeetCode 502 - IPO

The problem describes a scenario where we have a limited number of opportunities to invest in projects before an IPO.

leetcodehardarraygreedysortingheap-(priority-queue)

LeetCode Problem 502

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem describes a scenario where we have a limited number of opportunities to invest in projects before an IPO. Each project has two properties:

  • profits[i], the amount of capital gained after completing the project
  • capital[i], the minimum amount of capital required to start the project

We are also given:

  • k, the maximum number of projects we are allowed to complete
  • w, the initial amount of capital we currently have

The goal is to choose at most k distinct projects so that the final amount of capital is as large as possible.

A very important detail is that completing a project immediately increases our available capital. This means the order of project selection matters. A project that is impossible to start initially may become available after completing a profitable earlier project.

The input size is large:

  • n can be up to 100000
  • k can also be up to 100000

These constraints immediately rule out exponential or quadratic approaches. Any solution that repeatedly scans all projects inside another loop will likely time out.

The problem guarantees that the final answer fits within a 32-bit signed integer, so standard integer arithmetic is sufficient.

Several edge cases are important:

  • We may not be able to afford any project initially.
  • Some projects may have zero profit.
  • k may be larger than the number of projects.
  • Multiple projects may require the same capital.
  • Multiple projects may have identical profits.
  • A greedy choice that only looks at immediate profit without considering affordability could fail.

The core challenge is balancing two things simultaneously:

  • Which projects are currently affordable
  • Among affordable projects, which one gives the largest profit

Approaches

Brute Force Approach

A straightforward solution would try all possible combinations of up to k projects and compute the maximum achievable capital.

At each step, we would:

  1. Look at all unused projects.
  2. Find projects whose capital requirement is less than or equal to the current capital.
  3. Try every possible next project recursively.
  4. Track the best final capital.

This approach is correct because it explores every valid sequence of project selections. However, it is computationally infeasible.

In the worst case, the number of possible project sequences grows exponentially. Even with pruning, the search space becomes enormous for n = 100000.

Another slightly improved brute-force approach would repeatedly scan all projects to find the best affordable one. That still costs O(k * n), which is too slow when both values are large.

Key Insight

At every step, we only care about two things:

  • Which projects are currently affordable
  • Among those affordable projects, which one gives the maximum profit

This naturally suggests two operations:

  1. Efficiently add projects that become affordable as capital grows
  2. Efficiently retrieve the highest-profit affordable project

To support these efficiently:

  • Sort projects by required capital
  • Use a max-heap to store profits of currently affordable projects

The sorted list lets us process projects in increasing order of required capital. As our capital increases, we move newly affordable projects into the heap.

The heap ensures we always select the most profitable available project in O(log n) time.

This combination of sorting and a priority queue gives an efficient greedy solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) or O(k * n) O(n) Explores many project combinations or repeatedly scans all projects
Optimal O(n log n + k log n) O(n) Uses sorting and a max-heap to always choose the best affordable project

Algorithm Walkthrough

  1. Combine each project's capital requirement and profit into a single pair.

This makes it easy to sort and process projects together. Each project becomes:

(required_capital, profit)
  1. Sort all projects by required capital in ascending order.

This allows us to efficiently determine which projects become affordable as our current capital increases. 3. Create a max-heap to store profits of affordable projects.

Python's heapq is a min-heap by default, so we store negative profits to simulate a max-heap.

The heap represents all projects we can currently afford. 4. Maintain a pointer into the sorted project list.

This pointer tracks which projects have already been added to the heap. 5. Repeat at most k times.

Each iteration represents choosing one project. 6. Add all newly affordable projects to the heap.

While the current project's capital requirement is less than or equal to our current capital:

  • Push its profit into the heap
  • Move the pointer forward

This step ensures the heap always contains every project we can currently afford. 7. If the heap is empty, stop early.

An empty heap means there are no affordable projects left. Since we cannot increase our capital anymore, further progress is impossible. 8. Extract the most profitable project from the heap.

This greedy choice maximizes capital growth at the current step. 9. Add the selected profit to the current capital.

Completing the project increases available capital, potentially unlocking more projects in future iterations. 10. After completing at most k projects, return the final capital.

Why it works

The algorithm maintains an important invariant:

  • The heap always contains exactly the set of currently affordable projects that have not yet been chosen.

At every step, choosing the most profitable affordable project is optimal because additional capital can only increase future opportunities. A larger current capital can never reduce the set of projects we may choose later.

Therefore, greedily maximizing capital growth at each step leads to the globally optimal result.

Python Solution

from typing import List
import heapq

class Solution:
    def findMaximizedCapital(
        self,
        k: int,
        w: int,
        profits: List[int],
        capital: List[int]
    ) -> int:
        
        projects = list(zip(capital, profits))
        projects.sort()
        
        max_heap = []
        project_index = 0
        n = len(projects)
        
        for _ in range(k):
            
            while (
                project_index < n and
                projects[project_index][0] <= w
            ):
                required_capital, profit = projects[project_index]
                
                heapq.heappush(max_heap, -profit)
                project_index += 1
            
            if not max_heap:
                break
            
            w += -heapq.heappop(max_heap)
        
        return w

The implementation begins by combining and sorting projects by required capital. This preprocessing step ensures we can efficiently identify newly affordable projects as our capital grows.

The max_heap stores profits for all currently affordable projects. Since Python's heapq only supports min-heaps, profits are inserted as negative values.

The project_index pointer prevents us from repeatedly scanning the entire project list. Each project is processed exactly once and inserted into the heap only when it becomes affordable.

Inside the main loop, we first push every newly affordable project into the heap. After that, if the heap is empty, we know there are no projects we can perform, so we terminate early.

Otherwise, we pop the most profitable project and add its profit to our capital. This increases our ability to fund future projects.

The process repeats at most k times.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func findMaximizedCapital(
	k int,
	w int,
	profits []int,
	capital []int,
) int {

	n := len(profits)

	projects := make([][2]int, n)

	for i := 0; i < n; i++ {
		projects[i] = [2]int{capital[i], profits[i]}
	}

	sort.Slice(projects, func(i, j int) bool {
		return projects[i][0] < projects[j][0]
	})

	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	projectIndex := 0

	for i := 0; i < k; i++ {

		for projectIndex < n &&
			projects[projectIndex][0] <= w {

			heap.Push(maxHeap, projects[projectIndex][1])
			projectIndex++
		}

		if maxHeap.Len() == 0 {
			break
		}

		w += heap.Pop(maxHeap).(int)
	}

	return w
}

The Go solution follows the same algorithmic structure as the Python version. The main difference is that Go requires explicitly implementing the heap.Interface.

The custom MaxHeap reverses the comparison in the Less method so that the standard library heap behaves like a max-heap.

Go slices are dynamic, so heap insertion and removal work naturally through the interface methods.

Integer overflow is not a concern because the problem guarantees the answer fits within a 32-bit signed integer.

Worked Examples

Example 1

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

Sorted projects:

Project Required Capital Profit
0 0 1
1 1 2
2 1 3

Initial state:

Variable Value
Current Capital 0
Heap []
Project Index 0

Iteration 1

Affordable projects:

  • Project 0 requires capital 0

Heap after insertion:

Heap Contents
[1]

Choose maximum profit:

  • Select profit 1

Updated capital:

w = 0 + 1 = 1

Iteration 2

Newly affordable projects:

  • Project 1 requires capital 1
  • Project 2 requires capital 1

Heap after insertion:

Heap Contents
[3, 2]

Choose maximum profit:

  • Select profit 3

Updated capital:

w = 1 + 3 = 4

Final answer:

4

Example 2

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

Sorted projects:

Project Required Capital Profit
0 0 1
1 1 2
2 2 3

Iteration 1

Affordable projects:

  • Project 0

Heap:

[1]

Take profit 1:

w = 1

Iteration 2

Affordable projects:

  • Project 1

Heap:

[2]

Take profit 2:

w = 3

Iteration 3

Affordable projects:

  • Project 2

Heap:

[3]

Take profit 3:

w = 6

Final answer:

6

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + k log n) Sorting costs O(n log n), each heap operation costs O(log n)
Space O(n) The heap may contain up to n projects

The sorting step dominates the preprocessing cost. During the main loop, every project is inserted into the heap at most once and removed at most once. Heap operations are logarithmic, giving the overall complexity of O(n log n + k log n).

The heap can contain all projects in the worst case, so the auxiliary space complexity is O(n).

Test Cases

from typing import List

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

        projects = sorted(zip(capital, profits))

        max_heap = []
        project_index = 0
        n = len(projects)

        for _ in range(k):

            while (
                project_index < n and
                projects[project_index][0] <= w
            ):
                heapq.heappush(
                    max_heap,
                    -projects[project_index][1]
                )
                project_index += 1

            if not max_heap:
                break

            w += -heapq.heappop(max_heap)

        return w

solution = Solution()

assert solution.findMaximizedCapital(
    2, 0, [1, 2, 3], [0, 1, 1]
) == 4  # Provided example 1

assert solution.findMaximizedCapital(
    3, 0, [1, 2, 3], [0, 1, 2]
) == 6  # Provided example 2

assert solution.findMaximizedCapital(
    1, 0, [5], [0]
) == 5  # Single project

assert solution.findMaximizedCapital(
    3, 0, [1, 2, 3], [1, 1, 2]
) == 0  # Cannot afford any project initially

assert solution.findMaximizedCapital(
    5, 0, [1, 2], [0, 0]
) == 3  # k larger than number of projects

assert solution.findMaximizedCapital(
    3, 1, [0, 0, 10], [0, 1, 1]
) == 11  # Includes zero-profit projects

assert solution.findMaximizedCapital(
    2, 100, [1, 2, 3], [0, 50, 100]
) == 105  # Large starting capital

assert solution.findMaximizedCapital(
    4, 0, [1, 2, 3, 5], [0, 1, 1, 2]
) == 11  # Greedy selection chain

assert solution.findMaximizedCapital(
    2, 0, [1, 1, 1], [0, 0, 0]
) == 2  # Duplicate profits

assert solution.findMaximizedCapital(
    2, 0, [100, 1], [1, 0]
) == 101  # Unlock high-profit project later

Test Summary

Test Why
Example 1 Validates standard greedy behavior
Example 2 Validates repeated unlocking of projects
Single project Smallest valid input
No affordable projects Ensures early termination works
k larger than n Ensures loop handles exhaustion correctly
Zero-profit projects Verifies heap behavior with zero values
Large initial capital Ensures all projects become immediately available
Greedy selection chain Tests incremental capital growth
Duplicate profits Ensures duplicates are handled correctly
Unlocking later project Verifies future accessibility logic

Edge Cases

One important edge case occurs when no projects are affordable initially. For example, if w = 0 and every project requires at least 1 capital, the heap never receives any projects. A naive implementation might continue looping unnecessarily or attempt to pop from an empty heap. This solution explicitly checks whether the heap is empty and terminates early.

Another subtle edge case involves k being larger than the number of projects. Since the problem allows completing "at most" k projects, the algorithm must stop naturally once no projects remain. The heap-empty check handles this correctly without requiring special logic.

Projects with zero profit can also be tricky. A naive greedy strategy might incorrectly ignore them or mishandle heap ordering. This implementation treats zero-profit projects normally. They may still be useful if they unlock future profitable projects, although in this particular problem profits only increase capital directly.

A further edge case involves projects becoming affordable only after earlier selections. This is the central challenge of the problem. The sorted project list and incremental heap insertion ensure that every newly affordable project is considered exactly when it becomes available.