Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

IPO

Explore how to apply heaps to solve the IPO project selection problem where an investor aims to maximize final capital. Learn to manage project profits and capital requirements dynamically, and implement a strategy selecting up to k projects that optimizes returns under given constraints.

We'll cover the following...

Statement

An investor is looking to maximize their capital by undertaking a set of profitable projects. Due to limited time and resources, they can complete at most k distinct projects.

There are nn available projects. Each project i has:

  • A profit of profits[i] earned upon completion.

  • A minimum capital requirement of capital[i] needed to start the project.

The investor starts with an initial capital of c. After completing a project, its profit is immediately added to the investor's current capital.

The goal is to choose up to k different projects in a way that maximizes the investor’s final capital. Return the maximum capital achievable after completing these projects.

It is guaranteed that the answer fits within a 32-bit signed integer.

Constraints:

  • 1≤1 \leq k ≤103\leq 10^3

  • 0≤0 \leq c ≤\leq 10910^9

  • n==n== profits.length

  • n==n== capitals.length

  • 1≤n≤1031 \leq n \leq 10^3

  • 0≤0 \leqprofits[i] ≤104\leq 10^4

  • 0≤0 \leq capitals[i] ≤109\leq 10^9

Examples

canvasAnimation-image
1 / 3

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

IPO

1.

What is the maximum capital for the following input?

k =2= 2

c =1= 1

capitals =[1,2,3]= [1, 2, 3]

profits =[2,3,5]= [2, 3, 5]

A.

66

B.

55

C.

88

D.

1010

1 / 4

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5
6

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > MaximizeCapital.java
import java.util.*;
public class MaximizeCapital{
   public static int maximumCapital(int c, int k, int[] capitals,int[] profits) {
      
      // Replace this placeholder return statement with your code
         
      return -1;
   }
}
IPO