IPO

Master this topic with zero to advance depth.

IPO

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital. Return the maximized final capital.

Visual Representation

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

Initial Capital w = 0
Available Projects (capital <= 0): Project 0 (profit 1)

Do Project 0 -> w = 0 + 1 = 1
Projects left: 1 (cap:1, prof:2), 2 (cap:1, prof:3)
Available Projects (capital <= 1): Project 1, Project 2
Pick max profit: Project 2 (profit 3)

Do Project 2 -> w = 1 + 3 = 4
Max Capital = 4

Hard

Examples

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

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

Approach 1

Level I: Brute Force Greedy Selection

Intuition

To maximize our final capital, we should always greedily choose the project that we can afford (capital <= current w) and that yields the maximum profit. Once we finish it, our w increases, potentially unlocking new jobs. We can simply scan the list of projects up to k times, picking the best affordable project each time.

⏱ O(K * N) where N is the number of projects. For each of the K projects we want to complete, we might scan the entire array of N projects.💾 O(N) to keep track of which projects have been completed

Detailed Dry Run

k=2, w=0, prof=[1,2,3], cap=[0,1,1]

k=1: Scan all. P0(0<=0, prof 1), P1(1>0), P2(1>0). Best is P0. w=0+1=1. Mark P0 used.
k=2: Scan all. P0(used), P1(1<=1, prof 2), P2(1<=1, prof 3). Best is P2. w=1+3=4. Mark P2 used. Return w=4.

java

public class Main {
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        boolean[] used = new boolean[n];
        
        for (int i = 0; i < k; i++) {
            int maxProfit = -1;
            int bestIndex = -1;
            
            for (int j = 0; j < n; j++) {
                if (!used[j] && capital[j] <= w && profits[j] > maxProfit) {
                    maxProfit = profits[j];
                    bestIndex = j;
                }
            }
            
            if (bestIndex == -1) break; // Cannot afford any more projects
            used[bestIndex] = true;
            w += maxProfit;
        }
        
        return w;
    }

    public static void main(String[] args) {
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};
        System.out.println(findMaximizedCapital(2, 0, profits, capital)); // 4
    }
}

Approach 2

Level II: Sort Projects by Profit and Scan

Intuition

To improve our search for the maximum profit, we can sort all projects by their profit in descending order. Then, for each selection, we scan this sorted list from the beginning and pick the first project that we can afford (capital <= w). Once picked, we mark it used and repeat.

⏱ O(N log N + K * N) where N is the number of projects. Sorting takes N log N, and each of the K steps might scan up to N elements.💾 O(N) for the sorted list of projects and the used tracker

Detailed Dry Run

k=2, w=0, prof=[1,2,3], cap=[0,1,1] Sorted by Profit (desc): [(3,1), (2,1), (1,0)]

k=1: Scan. (3, cap:1 > 0) skip. (2, cap:1 > 0) skip. (1, cap:0 <= 0) PICK. w = 0 + 1 = 1.
k=2: Scan. (3, cap:1 <= 1) PICK. w = 1 + 3 = 4. Return w = 4.

java

import java.util.*;

public class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = profits[i];
            projects[i][1] = capital[i];
        }
        
        // Sort by profit descending
        Arrays.sort(projects, (a, b) -> Integer.compare(b[0], a[0]));
        
        boolean[] used = new boolean[n];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n; j++) {
                if (!used[j] && projects[j][1] <= w) {
                    w += projects[j][0];
                    used[j] = true;
                    break;
                }
            }
        }
        return w;
    }
}

Approach 3

Level III: Two Heaps (Optimal)

Intuition

Instead of scanning the whole array every time, we can maintain two collections: one for projects we CAN'T afford yet (sorted by capital required), and one for projects we CAN afford (sorted by profit). As our capital w grows, we transfer projects from the "can't afford" group to the "can afford" group. This perfectly maps to using a Min-Heap for capital and a Max-Heap for profits.

⏱ O(N log N) to sort projects and insert/remove from heaps. Extracting up to K items takes O(K log N).💾 O(N) for holding the projects and the priority queues.

Detailed Dry Run

k=2, w=0, prof=[1,2,3], cap=[0,1,1]

Pair & Sort by Capital: [(0,1), (1,2), (1,3)] -> Min-Heap equivalent.
w=0. Move affordable to Max-Heap (profits). Max-Heap gets (profit=1) from (0,1). Max-Heap = [1].
Can't move (1,2) or (1,3) since 1 > 0.
Do job 1 (k=1): pop Max-Heap (1). w = 0 + 1 = 1.
New w=1. Check Min-Heap. Both (1,2) and (1,3) are now affordable. Push their profits (2, 3) to Max-Heap. Max-Heap = [3, 2].
Do job 2 (k=2): pop Max-Heap (3). w = 1 + 3 = 4.
k=2 reached. Return w=4.

java

import java.util.*;

public class Main {
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        
        // Sort projects by capital required
        Arrays.sort(projects, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Max-Heap to store affordable profits
        PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        int ptr = 0;
        for (int i = 0; i < k; i++) {
            // Push all currently affordable projects to the max heap
            while (ptr < n && projects[ptr][0] <= w) {
                maxProfitHeap.offer(projects[ptr][1]);
                ptr++;
            }
            
            if (maxProfitHeap.isEmpty()) break;
            
            w += maxProfitHeap.poll();
        }
        
        return w;
    }

    public static void main(String[] args) {
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};
        System.out.println(findMaximizedCapital(2, 0, profits, capital)); // 4
    }
}

← Previous QuestionMinimum Cost to Hire K Workers

Next Question →Kth Smallest Element in Sorted Matrix

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.