IPO

HARD✓ CHIP-TIMEDLC #502 — FULL STATEMENT ↗

The drill: A startup can fund a limited number of projects in sequence, spending only the capital it currently holds; taking each round's most profitable affordable project maximizes the final treasury.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A startup can take on at most k projects, one at a time, starting with capital w already in hand.

Every project has its own required capital just to begin and its own profit paid out on completion; a finished project's profit feeds straight back into the treasury, potentially unlocking projects that weren't affordable before.

The final treasury should end up as large as possible after choosing the best sequence of up to k projects, and the answer is that single maximized capital total.

EX 01

k = 1 · w = 0 · profits = [5] · capital = [0]

→ 5

SINGLE PROJECT, IMMEDIATELY AFFORDABLE

EX 02

k = 1 · w = 0 · profits = [100] · capital = [5]

→ 0

THE ONLY PROJECT NEVER BECOMES AFFORDABLE

EX 03

k = 3 · w = 0 · profits = [7] · capital = [0]

→ 7

K EXCEEDS THE NUMBER OF PROJECTS, STOPS EARLY

project counts run up to several thousand
k, w, and all capital and profit values are non-negative
a project only becomes available once its capital requirement is met
fewer than k projects may be taken if none remain affordable

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Brute force rescans every unfunded project each round to find the best affordable one — that repeated scan is where the time goes. What if 'best affordable right now' didn't need a fresh scan every round?

HINT 2 THE STRUCTURE

Sort projects by required capital once. As the treasury grows, a pointer only ever moves forward through newly affordable projects — and a max-heap of their profits always has the best one on top.

HINT 3 ONE STEP FROM THE ANSWER

Sort by capital, then for each of the k rounds: push every project whose capital now fits into a max-heap, pop the highest profit, add it to the treasury, and stop early the moment the heap runs dry.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CAPITAL UNLOCKPATTERN · CAPITAL GATE + MAX HEAPk=3 · w=0 · projects (capital, profit): (0,1) (1,2) (3,10)

c0 p1

c1 p2

c3 p10

AFFORDABLE HEAP (PROFITS) · TREASURY

treasury → 0

heap → []

STEP 1

Treasury starts at 0, k=3 rounds allowed. Sorted by capital needed: project 0 (needs 0), project 1 (needs 1), project 2 (needs 3).

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/ipo.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(N LOG N + K LOG N)SPACE O(N)PYTHON · RACE PACE · 13 LN

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        n = len(profits)
        used = [False] * n
        for _ in range(k):
            best = -1
            for i in range(n):
                if not used[i] and capital[i] <= w:
                    if best == -1 or profits[i] > profits[best]:
                        best = i
            if best == -1:
                break
            used[best] = True
            w += profits[best]
        return w

TIME O(K·N)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (a, b) -> Integer.compare(capital[a], capital[b]));

        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        int i = 0;
        for (int round = 0; round < k; round++) {
            while (i < n && capital[order[i]] <= w) {
                heap.offer(profits[order[i]]);
                i++;
            }
            if (heap.isEmpty()) {
                break;
            }
            w += heap.poll();
        }
        return w;
    }
}

TIME O(N LOG N + K LOG N)SPACE O(N)JAVA · RACE PACE · 24 LN

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        boolean[] used = new boolean[n];
        for (int round = 0; round < k; round++) {
            int best = -1;
            for (int i = 0; i < n; i++) {
                if (!used[i] && capital[i] <= w) {
                    if (best == -1 || profits[i] > profits[best]) {
                        best = i;
                    }
                }
            }
            if (best == -1) {
                break;
            }
            used[best] = true;
            w += profits[best];
        }
        return w;
    }
}

TIME O(K·N)SPACE O(N)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED