Statement

A busy investor with an initial capital, c, needs an automated investment program. They can select k distinct projects from a list of n projects with corresponding capitals requirements and expected profits. For a given project ii, its capital requirement is capitals[i]capitals[i] , and the profit it yields is profits[i]profits[i].

The goal is to maximize their cumulative capital by selecting a maximum of k distinct projects to invest in, subject to the constraint that the investor’s current capital must be greater than or equal to the capital requirement of all selected projects.

When a selected project from the identified ones is finished, the pure profit from the project, along with the starting capital of that project is returned to the investor. This amount will be added to the total capital held by the investor. Now, the investor can invest in more projects with the new total capital. It is important to note that each project can only be invested once.

As a basic risk-mitigation measure, the investor wants to limit the number of projects they invest in. For example, if k is 22, the program should identify the two projects that maximize the investor’s profits while ensuring that the investor’s capital is sufficient to invest in the projects.

Overall, the program should help the investor to make informed investment decisions by picking a list of a maximum of k distinct projects to maximize the final profit while mitigating the risk.

Constraints:

  • 1≤1 \leq k ≤103\leq 10^3
  • 0≤0 \leq c ≤109\leq 10^9
  • 1≤1 \leq n ≤103\leq 10^3
  • k ≤\leq n
  • n ==== profits.length
  • n ==== capitals.length
  • 0≤0 \leq profits[i] ≤104\leq 10^4
  • 0≤0 \leq capitals[i] ≤109\leq 10^9

Solution

You may have already brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach is to traverse every value of the capitals array based on the available capital. If the current capital is less than or equal to the capital value in the array, then store the profit value in a new array that corresponds to the capital index. Whenever the current capital becomes less than the capital value in the array, we’ll select the project with the largest profit value. The selected profit value will be added to the previous capital. Repeat this process until we get the required number of projects containing the maximum profit.

We got the solution we needed, but at what cost? The time complexity is O(n2)O(n^2), where n represents the number of projects. This is because we need O(n)O(n) time to traverse the capitals array in order to find affordable projects. Additonally, for each subset of affordable projects, we would need another O(n)O(n) search to narrow down the project list to the one that yields the highest profit. The space complexity for storing the profit values in a new array is O(n)O(n).

Optimized approach using two heaps

This approach optimizes the selection of projects to maximize capital using a two-heap method. By pushing projects’ capital into a min-heap, projects are organized in ascending order of capital needed. Then, we choose projects from the min-heap that fit within our available capital, prioritizing those with the lowest costs. The selected projects are evaluated for their profitability by inserting their profits into a max-heap. This allows for prioritizing projects based on their potential return on investment. The most profitable project from the max-heap is chosen, and its profit is added to the current capital. The selected project is excluded from the list of available projects, and the same steps are repeated with the updated capital to select the next project. This process—selecting projects based on the capital requirement, evaluating project affordability, selecting for maximum profit, and updating available capital—is repeated for kk times to select kk projects that yield maximum profit.

The slide deck below illustrates the key steps of the solution, with k =2= 2 and c =1= 1:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to the Just the code section.

Step-by-step solution construction

Here are the steps required to solve this problem:

We’ll push all the capitals values in a min-heap to pick the required number of projects, starting from the one with the lowest capital requirement.

class MaximizeCapital {
	
	public static int maximumCapital(int c, int k, int[] capitals, int[] profits) {
		PriorityQueue<Integer> capitalMinHeap = new PriorityQueue<Integer>();
		int i = 0;
		// Insert all capitals values to a min-heap
		while (i<capitals.length) {
			capitalMinHeap.add(capitals[i]);
			
			i++;
		}
		printCapitalsMinHeap(capitalMinHeap);
		return 0;
	}
	static void printCapitalsMinHeap(PriorityQueue<Integer> capitals)
    {
		List<Integer> l = new ArrayList<>();
		while(!capitals.isEmpty()){
			l.add(capitals.peek());
			capitals.poll();
		}
		System.out.println("\t"+ l.toString());
    }
	public static void main(String[] args) {
		int[] c = { 1, 2, 1, 7, 2 };
		int[] k = { 2, 3, 3, 2, 4 };
		int[][] capitals = {
			{1, 2, 2, 3}, 
      		{1, 3, 4, 5, 6}, 
      		{1, 2, 3, 4}, 
      		{6, 7, 8, 10}, 
      		{2, 3, 5, 6, 8, 12}
		};
		int[][] profits = {
			{2, 4, 6, 8}, 
        	{1, 2, 3, 4, 5}, 
        	{1, 3, 5, 7}, 
        	{4, 8, 12, 14}, 
        	{1, 2, 5, 6, 8, 9}
		};
		for (int i = 0; i<k.length; i++) {
			System.out.println((i + 1) + ".\tGiven capitals: " + Arrays.toString(capitals[i]));
			System.out.println("  \tAdding capital values...");
			maximumCapital(c[i], k[i], capitals[i], profits[i]);
			System.out.println(PrintHyphens.repeat("-", 100));
		}
	}
}
IPO

Let’s identify all the projects whose capital requirements are less than or equal to our current capital and push the profits yielded by these projects onto the max-heap.

Assume the current capital is fixed as 22.

class MaximizeCapital {
	
	public static int maximumCapital(int c, int k, int[] capitals, int[] profits) {
		int currentCapital = 2;
		PriorityQueue<Integer> profitsMaxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        
		System.out.println("\tIdentifying projects we can afford with our current capital of " + currentCapital);
		int i = 0;
        // Select projects (in the range of the current capital)
        // then push them onto the max-heap
		while (i<profits.length) {
			if(capitals[i] <= currentCapital){
                profitsMaxHeap.add(profits[i]);
				System.out.println("\t\tProfit of project (with capital requirement of " +
		        currentCapital + " pushed on to max-heap = " + profits[i]);
			}
			
			i++;
		}
		
		return 0;
	}
	
	public static void main(String[] args) {
		int[] c = { 1, 2, 1, 7, 2 };
		int[] k = { 2, 3, 3, 2, 4 };
		int[][] capitals = {
			{1, 2, 2, 3}, 
      		{1, 3, 4, 5, 6}, 
      		{1, 2, 3, 4}, 
      		{2, 7, 8, 10}, 
      		{2, 3, 5, 6, 8, 12}
		};
		int[][] profits = {
			{2, 4, 6, 8}, 
        	{1, 2, 3, 4, 5}, 
        	{1, 3, 5, 7}, 
        	{4, 8, 12, 14}, 
        	{1, 2, 5, 6, 8, 9}
		};
		for (int i = 0; i<k.length; i++) {
			System.out.println((i + 1) + ".\tGiven profits: " + Arrays.toString(profits[i]));
			System.out.println("  \tSelecting profits...");
			maximumCapital(c[i], k[i], capitals[i], profits[i]);
			System.out.println(PrintHyphens.repeat("-", 100) + "\n");
		}
	}
}
IPO

Now, we can select the most affordable project that yields the highest profit. We’ll add the profit from every selected project to the previous capital to calculate the maximum capital we can accumulate. We need to do this after each project selection as more capital will typically allow us to choose from a larger subset of projects. In case no profit is pushed onto the max-heap, we break out of the loop.

Here’s the complete solution to calculate the maximum capital:

class MaximizeCapital {
	public static int maximumCapital(int c, int k, int[] capitals, int[] profits) {
        int n = capitals.length;
		int currentCapital = c;
		// Insert all capitals values to a min-heap
        PriorityQueue<int[]> capitalMinHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < n; ++i) {
            capitalMinHeap.offer(new int[] {capitals[i], i});
        }
        PriorityQueue<int[]> profitsMaxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
		int i = 0;
		// Calculate capital of all the required number of projects
        // containing maximum profit
        while (i < k) {
			// Select projects (in the range of the current capital)
            // then push them onto the max-heap
            while (!capitalMinHeap.isEmpty() && capitalMinHeap.peek()[0] <= currentCapital) {
				int[] j = capitalMinHeap.poll();
                profitsMaxHeap.offer(new int[]{profits[j[1]]});
            }
			// check if the max-heap is empty
            if (profitsMaxHeap.isEmpty()) {
                break;
            }
			// Select those projects from the max-heap that contain the maximum profit
			int x = profitsMaxHeap.poll()[0];
			System.out.println("\t\tUpdated capital = "+ currentCapital + " + "+ x);
            currentCapital += x;
			i++;
        }
        return currentCapital;
    }
	public static void main(String[] args) {
		int[] c = { 0, 1, 2, 1, 7, 2 };
		int[] k = { 1, 2, 3, 3, 2, 4 };
		int[][] capitals = {
			{1, 1, 2},
			{1, 2, 2, 3}, 
      		{1, 3, 4, 5, 6}, 
      		{1, 2, 3, 4}, 
      		{6, 7, 8, 10}, 
      		{2, 3, 5, 6, 8, 12}
		};
		int[][] profits = {
			{1, 2, 3},
			{2, 4, 6, 8}, 
        	{1, 2, 3, 4, 5}, 
        	{1, 3, 5, 7}, 
        	{4, 8, 12, 14}, 
        	{1, 2, 5, 6, 8, 9}
		};
		for (int i = 0; i<k.length; i++) {
			System.out.println((i + 1) + ".\tProject capital requirements: " + Arrays.toString(capitals[i]));
			System.out.println("\tProject expected profits: " + Arrays.toString(profits[i]));
			System.out.println("\tNumber of projects: " + k[i]);
			System.out.println("\tStart-up capital: " + c[i]);
			System.out.println("\n\t\tProcessing: ");
			System.out.println("\n\tMaximum Capital earned: " + maximumCapital(c[i], k[i], capitals[i], profits[i]));
			System.out.println(PrintHyphens.repeat("-", 100));
		}
	}
}
IPO

Just the code

Here’s the complete solution to this problem:

class MaximizeCapital {
	public static int maximumCapital(int c, int k, int[] capitals, int[] profits) {
        int n = capitals.length;
		int currentCapital = c;
        PriorityQueue<int[]> capitalMinHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < n; ++i) {
            capitalMinHeap.offer(new int[] {capitals[i], i});
        }
        PriorityQueue<int[]> profitsMaxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
		int i = 0;
        while (i < k) {
            while (!capitalMinHeap.isEmpty() && capitalMinHeap.peek()[0] <= currentCapital) {
				int[] j = capitalMinHeap.poll();
                profitsMaxHeap.offer(new int[]{profits[j[1]]});
            }
            if (profitsMaxHeap.isEmpty()) {
                break;
            }
			int x = profitsMaxHeap.poll()[0];
            currentCapital += x;
			i++;
        }
        return currentCapital;
    }
	public static void main(String[] args) {
		int[] c = { 0, 1, 2, 1, 7, 2 };
		int[] k = { 1, 2, 3, 3, 2, 4 };
		int[][] capitals = {
			{1, 1, 2},
			{1, 2, 2, 3}, 
      		{1, 3, 4, 5, 6}, 
      		{1, 2, 3, 4}, 
      		{6, 7, 8, 10}, 
      		{2, 3, 5, 6, 8, 12}
		};
		int[][] profits = {
			{1, 2, 3},
			{2, 4, 6, 8}, 
        	{1, 2, 3, 4, 5}, 
        	{1, 3, 5, 7}, 
        	{4, 8, 12, 14}, 
        	{1, 2, 5, 6, 8, 9}
		};
		for (int i = 0; i<k.length; i++) {
			System.out.println((i + 1) + ".\tProject capital requirements: " + Arrays.toString(capitals[i]));
			System.out.println("\tProject expected profits: " + Arrays.toString(profits[i]));
			System.out.println("\tNumber of projects: " + k[i]);
			System.out.println("\tStart-up capital: " + c[i]);
			System.out.println("\n\tMaximum Capital earned: " + maximumCapital(c[i], k[i], capitals[i], profits[i]));
			System.out.println(PrintHyphens.repeat("-", 100));
		}
	}
}
IPO

Solution summary

To recap, the solution to this problem can be divided into the following four steps:

  1. Push all capitals values in a min-heap.

  2. Select projects that can be invested in the range of the current capital and push their profits in a max-heap.

  3. Select the project from the max-heap that yields the maximum profit.

  4. Add the profit from the selected project to the current capital.

Repeat steps 22–44 until k projects have been selected.

Time complexity

The time complexity to push the required capitals values in the min-heap is O(nlog⁡n)O(n \log n), where nn represents the number of projects. The time complexity to select the projects with the maximum profits from the heaps is O(klog⁡n)O(k \log n), where kk represents the number of selected projects. Therefore, the total time complexity comes out to be O(nlog⁡n+klog⁡n)O(n \log n + k \log n), that is, O((n+k)log⁡n)O((n+k) \log n). Since the upper bound on kk is nn, the worst case is when k=nk=n. We can express the worst-case time complexity as O((n+n)log⁡n)O((n+n) \log n), which is O(nlog⁡n)O(n \log n).

Space complexity

We’re using two heaps, one to store capitals and one to store profits. In the worst case, where we meet the capital requirements of all the projects right from the start, we populate both heaps with nn elements each. Hence, the space complexity of this solution is O(n)O(n).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.