502. IPO

At a Glance

Topic: heap-priority-queue
Pattern: Top-K / Heap (greedy + max-heap of profits)
Difficulty: Hard
Companies: Google, Amazon, Meta, Microsoft
Frequency: Medium
LeetCode: 502

You have maxProjects rounds. In each round you may start at most one project; project index needs capital[index] starting capital and pays profits[index]. Start with initialCapital. Maximize final capital.

Recognition Cues

“Choose up to k projects” with affordability rule
Per round, among affordable projects, take max profit — greedy is optimal
Max-heap of candidate profits; advance pointer in sorted-by-capital list

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — backtrack / enumerate subsets of up to maxProjects projects — exponential in n.
Acceptable — rescan all remaining projects each round for max profit under current capital — O(maxProjects · n) without heap; correct but loses log factor.
Optimal — sort by required capital; maintain pointer into that order; each round push all newly affordable profits into a max-heap, take top — O(n log n + k log n) dominated by sort + k pops; space O(n).

Optimal Solution

Go

import (
	"container/heap"
	"sort"
)

type IntMaxHeap []int

func (values IntMaxHeap) Len() int { return len(values) }
func (values IntMaxHeap) Less(indexA, indexB int) bool {
	return values[indexA] > values[indexB]
}
func (values IntMaxHeap) Swap(indexA, indexB int) {
	values[indexA], values[indexB] = values[indexB], values[indexA]
}
func (values *IntMaxHeap) Push(value any) { *values = append(*values, value.(int)) }
func (values *IntMaxHeap) Pop() any {
	old := *values
	lastIndex := len(old) - 1
	item := old[lastIndex]
	*values = old[:lastIndex]
	return item
}

type project struct {
	requiredCapital int
	profit          int
}

func findMaximizedCapital(maxProjects int, initialCapital int, profits []int, capitals []int) int {
	projects := make([]project, len(profits))
	for index := range profits {
		projects[index] = project{requiredCapital: capitals[index], profit: profits[index]}
	}
	sort.Slice(projects, func(indexA, indexB int) bool {
		return projects[indexA].requiredCapital < projects[indexB].requiredCapital
	})
	profitHeap := &IntMaxHeap{}
	heap.Init(profitHeap)
	nextAvailable := 0
	currentCapital := initialCapital
	for round := 0; round < maxProjects; round++ {
		for nextAvailable < len(projects) && projects[nextAvailable].requiredCapital <= currentCapital {
			heap.Push(profitHeap, projects[nextAvailable].profit)
			nextAvailable++
		}
		if profitHeap.Len() == 0 {
			break
		}
		// invariant: we picked the single best profit among all projects affordable right now
		currentCapital += heap.Pop(profitHeap).(int)
	}
	return currentCapital
}

JavaScript

class MaxHeap {
	constructor() {
		this.values = [];
	}
	push(value) {
		this.values.push(value);
		this.bubbleUp(this.values.length - 1);
	}
	pop() {
		const top = this.values[0];
		const last = this.values.pop();
		if (this.values.length > 0) {
			this.values[0] = last;
			this.bubbleDown(0);
		}
		return top;
	}
	get length() {
		return this.values.length;
	}
	bubbleUp(index) {
		while (index > 0) {
			const parentIndex = Math.floor((index - 1) / 2);
			if (this.values[parentIndex] >= this.values[index]) {
				break;
			}
			[this.values[parentIndex], this.values[index]] = [
				this.values[index],
				this.values[parentIndex],
			];
			index = parentIndex;
		}
	}
	bubbleDown(index) {
		const length = this.values.length;
		while (true) {
			const leftIndex = index * 2 + 1;
			const rightIndex = index * 2 + 2;
			let largest = index;
			if (
				leftIndex < length &&
				this.values[leftIndex] > this.values[largest]
			) {
				largest = leftIndex;
			}
			if (
				rightIndex < length &&
				this.values[rightIndex] > this.values[largest]
			) {
				largest = rightIndex;
			}
			if (largest === index) {
				break;
			}
			[this.values[index], this.values[largest]] = [
				this.values[largest],
				this.values[index],
			];
			index = largest;
		}
	}
}

function findMaximizedCapital(maxProjects, initialCapital, profits, capitals) {
	const projects = profits.map((profit, index) => ({
		requiredCapital: capitals[index],
		profit,
	}));
	projects.sort(
		(projectA, projectB) =>
			projectA.requiredCapital - projectB.requiredCapital,
	);
	const profitHeap = new MaxHeap();
	let nextAvailable = 0;
	let currentCapital = initialCapital;
	for (let round = 0; round < maxProjects; round++) {
		while (
			nextAvailable < projects.length &&
			projects[nextAvailable].requiredCapital <= currentCapital
		) {
			profitHeap.push(projects[nextAvailable].profit);
			nextAvailable++;
		}
		if (profitHeap.length === 0) {
			break;
		}
		currentCapital += profitHeap.pop();
	}
	return currentCapital;
}

Walkthrough

Sort by capital; advance nextAvailable as money grows; each round take largest profit among affordable.

Invariant: postponing a higher-profit affordable project for a lower one never helps next rounds’ capital earlier.

Edge Cases

maxProjects == 0
Can afford no project initially — stay flat
All projects affordable from start — always pop max profit k times

Pitfalls

Sorting by profit instead of processing affordable set dynamically
Using min-heap on capital without pairing profits correctly

Variants

Unbounded k or profit tied to time — different models; clarify constraints.
Multiple parallel workers — becomes scheduling / knapsack-like.
Profits with capital return after delay — time-expanded graph (not this greedy).

Mind-Map Tags

#heap #greedy #sort-by-capital #k-rounds #maximize-capital #feasible-set