IPO (Maximize Capital, K Projects)

🎯

IPO (Maximize Capital, K Projects)

hardHEAPAmazonGoogleFacebook

Imagine you are an investor with limited initial capital and a list of potential projects, each requiring some capital to start and yielding a profit. You want to maximize your capital after completing at most K projects by choosing the most profitable projects you can afford at each step.

💡 This problem is about making optimal choices under constraints. Beginners often struggle because it requires managing two conditions simultaneously: capital availability and profit maximization. The challenge is to efficiently pick projects that can be started with current capital and yield the highest profit to increase capital for future projects.

📋

Problem Statement

You are given an initial capital W, an integer K representing the maximum number of projects you can complete, and two arrays: Profits and Capital, each of length n. Profits[i] is the profit of the i-th project, and Capital[i] is the minimum capital required to start the i-th project. You can only start a project if your current capital is at least Capital[i]. After completing a project, your capital increases by its profit. Return the maximum capital you can have after completing at most K projects.

1 ≤ n ≤ 10^50 ≤ K ≤ 10^50 ≤ W ≤ 10^90 ≤ Profits[i], Capital[i] ≤ 10^9

💡

Example

Input"K = 2, W = 0, Profits = [1,2,3], Capital = [0,1,1]"

Output4

Start with capital 0, pick project 0 (profit 1), capital becomes 1. Now capital is 1, pick project 2 (profit 3), capital becomes 4. Maximum capital after 2 projects is 4.

• K = 0 → output should be initial capital W
• All projects require more capital than W → output should be W
• Profits are zero for all projects → capital remains unchanged after projects
• Capital and profits arrays are empty → output should be W

⚠️

Common Mistakes

Not sorting projects by capital before processing

Cannot efficiently find affordable projects, leading to incorrect or slow solutions

✅ Sort projects by capital ascending before processing

Using a min-heap for profits instead of max-heap

Always picks the least profitable project, resulting in suboptimal capital gain

✅ Use a max-heap (or simulate with negative values) for profits

Not breaking early when no projects are affordable

Unnecessary iterations wasting time, possibly causing timeouts

✅ Break the loop if max-profit heap is empty

Modifying input arrays directly or not handling duplicates properly

May cause incorrect results or runtime errors

✅ Use separate data structures and track visited projects if needed

Confusing capital and profit arrays indices

Mixing up capital and profit leads to wrong project selection

✅ Always keep capital and profit paired correctly

🧠

Brute Force (Pure Recursion / Nested Loops / etc.)

💡 This approach exists to build intuition by exploring all possible project selections without optimization. It helps understand the problem's combinatorial nature and why naive solutions are inefficient.

Intuition

Try every possible project that can be started with current capital, recursively explore the outcomes of picking each project, and keep track of the maximum capital achievable after K projects.

Algorithm

1. If no projects can be done or K is 0, return current capital.
2. For each project that can be started with current capital and not yet done:
3. Recursively compute the maximum capital after picking that project and reducing K by 1.
4. Return the maximum capital found among all choices.

💡 The recursion explores all combinations, which is conceptually simple but leads to exponential time due to repeated work and many branches.

</>

Code

def findMaxCapital(K, W, Profits, Capital):
    n = len(Profits)
    visited = [False] * n

    def dfs(k, w):
        if k == 0:
            return w
        max_capital = w
        for i in range(n):
            if not visited[i] and Capital[i] <= w:
                visited[i] = True
                current = dfs(k - 1, w + Profits[i])
                max_capital = max(max_capital, current)
                visited[i] = False
        return max_capital

    return dfs(K, W)

# Driver code
if __name__ == '__main__':
    K = 2
    W = 0
    Profits = [1, 2, 3]
    Capital = [0, 1, 1]
    print(findMaxCapital(K, W, Profits, Capital))  # Output: 4

Line Notes

def findMaxCapital(K, W, Profits, Capital):Defines main function with inputs K, W, Profits, Capital to solve problem

visited = [False] * nTracks which projects have been chosen to avoid repeating the same project

def dfs(k, w):Recursive helper function exploring all project choices with k picks left and current capital w

if k == 0:Base case: no projects left to pick, return current capital as result

for i in range(n):Iterate over all projects to find those affordable and not yet chosen

if not visited[i] and Capital[i] <= w:Only consider projects that can be started with current capital and not already done

visited[i] = TrueMark project as chosen before recursive call to avoid reuse

current = dfs(k - 1, w + Profits[i])Recursively compute max capital after picking project i and reducing picks

max_capital = max(max_capital, current)Update max capital found among all recursive branches

visited[i] = FalseBacktrack to allow other project choices in different branches

return max_capitalReturn the best capital achievable from this state

import java.util.*;
public class IPOBruteForce {
    public static int findMaxCapital(int K, int W, int[] Profits, int[] Capital) {
        int n = Profits.length;
        boolean[] visited = new boolean[n];
        return dfs(K, W, Profits, Capital, visited);
    }

    private static int dfs(int k, int w, int[] Profits, int[] Capital, boolean[] visited) {
        if (k == 0) return w;
        int maxCapital = w;
        for (int i = 0; i < Profits.length; i++) {
            if (!visited[i] && Capital[i] <= w) {
                visited[i] = true;
                int current = dfs(k - 1, w + Profits[i], Profits, Capital, visited);
                maxCapital = Math.max(maxCapital, current);
                visited[i] = false;
            }
        }
        return maxCapital;
    }

    public static void main(String[] args) {
        int K = 2;
        int W = 0;
        int[] Profits = {1, 2, 3};
        int[] Capital = {0, 1, 1};
        System.out.println(findMaxCapital(K, W, Profits, Capital)); // Output: 4
    }
}

Line Notes

public static int findMaxCapital(int K, int W, int[] Profits, int[] Capital)Main function signature to solve problem with given inputs

boolean[] visited = new boolean[n];Boolean array to track chosen projects and avoid repeats

private static int dfs(int k, int w, int[] Profits, int[] Capital, boolean[] visited)Recursive helper exploring all project choices with k picks left and capital w

if (k == 0) return w;Base case: no picks left, return current capital

for (int i = 0; i < Profits.length; i++)Try all projects to find affordable and unchosen ones

if (!visited[i] && Capital[i] <= w)Only pick projects affordable with current capital and not chosen

visited[i] = true;Mark project chosen before recursion

int current = dfs(k - 1, w + Profits[i], Profits, Capital, visited);Recurse with updated capital and picks

maxCapital = Math.max(maxCapital, current);Update max capital found

visited[i] = false;Backtrack to explore other choices

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dfs(int k, int w, const vector<int>& Profits, const vector<int>& Capital, vector<bool>& visited) {
    if (k == 0) return w;
    int maxCapital = w;
    for (int i = 0; i < Profits.size(); i++) {
        if (!visited[i] && Capital[i] <= w) {
            visited[i] = true;
            int current = dfs(k - 1, w + Profits[i], Profits, Capital, visited);
            maxCapital = max(maxCapital, current);
            visited[i] = false;
        }
    }
    return maxCapital;
}

int findMaxCapital(int K, int W, vector<int>& Profits, vector<int>& Capital) {
    vector<bool> visited(Profits.size(), false);
    return dfs(K, W, Profits, Capital, visited);
}

int main() {
    int K = 2;
    int W = 0;
    vector<int> Profits = {1, 2, 3};
    vector<int> Capital = {0, 1, 1};
    cout << findMaxCapital(K, W, Profits, Capital) << endl; // Output: 4
    return 0;
}

Line Notes

int dfs(int k, int w, const vector<int>& Profits, const vector<int>& Capital, vector<bool>& visited)Recursive helper exploring all project choices with k picks left and capital w

if (k == 0) return w;Base case: no picks left, return current capital

for (int i = 0; i < Profits.size(); i++)Try all projects to find affordable and unchosen ones

if (!visited[i] && Capital[i] <= w)Only pick projects affordable with current capital and not chosen

visited[i] = true;Mark project chosen before recursion

int current = dfs(k - 1, w + Profits[i], Profits, Capital, visited);Recurse with updated capital and picks

maxCapital = max(maxCapital, current);Update max capital found

visited[i] = false;Backtrack to explore other choices

vector<bool> visited(Profits.size(), false);Initialize visited array to track chosen projects

function findMaxCapital(K, W, Profits, Capital) {
    const n = Profits.length;
    const visited = new Array(n).fill(false);

    function dfs(k, w) {
        if (k === 0) return w;
        let maxCapital = w;
        for (let i = 0; i < n; i++) {
            if (!visited[i] && Capital[i] <= w) {
                visited[i] = true;
                const current = dfs(k - 1, w + Profits[i]);
                maxCapital = Math.max(maxCapital, current);
                visited[i] = false;
            }
        }
        return maxCapital;
    }

    return dfs(K, W);
}

// Test
console.log(findMaxCapital(2, 0, [1, 2, 3], [0, 1, 1])); // Output: 4

Line Notes

function findMaxCapital(K, W, Profits, Capital)Main function with inputs to solve problem

const visited = new Array(n).fill(false);Track chosen projects to avoid repeats

function dfs(k, w)Recursive helper exploring all project choices with k picks left and capital w

if (k === 0) return w;Base case: no picks left, return current capital

for (let i = 0; i < n; i++)Try all projects to find affordable and unchosen ones

if (!visited[i] && Capital[i] <= w)Only pick projects affordable with current capital and not chosen

visited[i] = true;Mark project chosen before recursion

const current = dfs(k - 1, w + Profits[i]);Recurse with updated capital and picks

maxCapital = Math.max(maxCapital, current);Update max capital found

visited[i] = false;Backtrack to explore other choices

⏱

Complexity

TimeO(n^K)

SpaceO(n)

At each of K steps, we try up to n projects, leading to exponential branching. The visited array uses O(n) space.

💡 For n=10 and K=3, this means up to 10^3=1000 recursive calls, which grows quickly and becomes infeasible for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Sorting + Two Heaps (Greedy with Max-Heap and Min-Heap)

💡 This approach efficiently picks the most profitable projects available at each step by using two heaps: one to track projects by capital requirement and another to pick the max profit among affordable projects.

Intuition

Sort projects by capital required. Use a min-heap to quickly find projects affordable with current capital. Move affordable projects to a max-heap by profit. At each step, pick the project with the highest profit from the max-heap to maximize capital gain.

Algorithm

1. Pair each project’s capital and profit, then sort projects by capital ascending.
2. Initialize a max-heap for profits.
3. For up to K projects:
4. Move all projects affordable with current capital from sorted list to max-heap.
5. If max-heap is empty, break early as no projects can be started.
6. Pop the max profit project from max-heap and add its profit to capital.
7. Return the final capital.

💡 This approach cleverly uses heaps to efficiently manage which projects are available and which to pick next, avoiding brute force.

</>

Code

import heapq

def findMaxCapital(K, W, Profits, Capital):
    n = len(Profits)
    projects = sorted(zip(Capital, Profits), key=lambda x: x[0])
    max_profit_heap = []
    i = 0

    for _ in range(K):
        while i < n and projects[i][0] <= W:
            heapq.heappush(max_profit_heap, -projects[i][1])
            i += 1
        if not max_profit_heap:
            break
        W += -heapq.heappop(max_profit_heap)
    return W

# Driver code
if __name__ == '__main__':
    K = 2
    W = 0
    Profits = [1, 2, 3]
    Capital = [0, 1, 1]
    print(findMaxCapital(K, W, Profits, Capital))  # Output: 4

Line Notes

projects = sorted(zip(Capital, Profits), key=lambda x: x[0])Sort projects by capital required ascending to process affordable projects efficiently

max_profit_heap = []Max-heap (using negative profits) to pick most profitable projects available

while i < n and projects[i][0] <= W:Add all projects affordable with current capital to max-profit heap

heapq.heappush(max_profit_heap, -projects[i][1])Push negative profit to simulate max-heap behavior with min-heap

if not max_profit_heap:If no projects are affordable, break early to avoid unnecessary iterations

W += -heapq.heappop(max_profit_heap)Pick project with max profit and add its profit to current capital

import java.util.*;
public class IPOTwoHeaps {
    public static int findMaxCapital(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];
        }
        Arrays.sort(projects, Comparator.comparingInt(a -> a[0]));

        PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());
        int i = 0;

        for (int k = 0; k < K; k++) {
            while (i < n && projects[i][0] <= W) {
                maxProfitHeap.offer(projects[i][1]);
                i++;
            }
            if (maxProfitHeap.isEmpty()) break;
            W += maxProfitHeap.poll();
        }
        return W;
    }

    public static void main(String[] args) {
        int K = 2;
        int W = 0;
        int[] Profits = {1, 2, 3};
        int[] Capital = {0, 1, 1};
        System.out.println(findMaxCapital(K, W, Profits, Capital)); // Output: 4
    }
}

Line Notes

int[][] projects = new int[n][2];Pair capital and profit for each project to sort and process efficiently

Arrays.sort(projects, Comparator.comparingInt(a -> a[0]));Sort projects by capital ascending to find affordable projects quickly

PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());Max-heap to pick projects with highest profit

while (i < n && projects[i][0] <= W)Add all projects affordable with current capital to max-profit heap

maxProfitHeap.offer(projects[i][1]);Add profit to max-heap

if (maxProfitHeap.isEmpty()) break;If no projects affordable, break early to save time

W += maxProfitHeap.poll();Pick project with max profit and add to capital

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int findMaxCapital(int K, int W, vector<int>& Profits, vector<int>& Capital) {
    int n = Profits.size();
    vector<pair<int,int>> projects;
    for (int i = 0; i < n; i++) {
        projects.emplace_back(Capital[i], Profits[i]);
    }
    sort(projects.begin(), projects.end());

    priority_queue<int> maxProfitHeap;
    int i = 0;

    for (int k = 0; k < K; k++) {
        while (i < n && projects[i].first <= W) {
            maxProfitHeap.push(projects[i].second);
            i++;
        }
        if (maxProfitHeap.empty()) break;
        W += maxProfitHeap.top();
        maxProfitHeap.pop();
    }
    return W;
}

int main() {
    int K = 2;
    int W = 0;
    vector<int> Profits = {1, 2, 3};
    vector<int> Capital = {0, 1, 1};
    cout << findMaxCapital(K, W, Profits, Capital) << endl; // Output: 4
    return 0;
}

Line Notes

vector<pair<int,int>> projects;Pair capital and profit for each project to sort and process efficiently

sort(projects.begin(), projects.end());Sort projects by capital ascending to find affordable projects quickly

priority_queue<int> maxProfitHeap;Max-heap to pick projects with highest profit

while (i < n && projects[i].first <= W)Add all projects affordable with current capital to max-profit heap

maxProfitHeap.push(projects[i].second);Push profit into max-heap

if (maxProfitHeap.empty()) break;If no projects affordable, break early to save time

W += maxProfitHeap.top();Pick project with max profit and add to capital

maxProfitHeap.pop();Remove chosen project from heap

function findMaxCapital(K, W, Profits, Capital) {
    const n = Profits.length;
    const projects = Capital.map((c, i) => [c, Profits[i]]).sort((a, b) => a[0] - b[0]);
    const maxProfitHeap = [];

    function heapPush(heap, val) {
        heap.push(val);
        let i = heap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (heap[parent] >= heap[i]) break;
            [heap[parent], heap[i]] = [heap[i], heap[parent]];
            i = parent;
        }
    }

    function heapPop(heap) {
        const top = heap[0];
        const end = heap.pop();
        if (heap.length > 0) {
            heap[0] = end;
            let i = 0;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, largest = i;
                if (left < heap.length && heap[left] > heap[largest]) largest = left;
                if (right < heap.length && heap[right] > heap[largest]) largest = right;
                if (largest === i) break;
                [heap[i], heap[largest]] = [heap[largest], heap[i]];
                i = largest;
            }
        }
        return top;
    }

    let i = 0;
    for (let k = 0; k < K; k++) {
        while (i < n && projects[i][0] <= W) {
            heapPush(maxProfitHeap, projects[i][1]);
            i++;
        }
        if (maxProfitHeap.length === 0) break;
        W += heapPop(maxProfitHeap);
    }
    return W;
}

// Test
console.log(findMaxCapital(2, 0, [1, 2, 3], [0, 1, 1])); // Output: 4

Line Notes

const projects = Capital.map((c, i) => [c, Profits[i]]).sort((a, b) => a[0] - b[0]);Pair and sort projects by capital ascending to process affordable projects efficiently

function heapPush(heap, val)Helper function to push value into max-heap maintaining heap property

function heapPop(heap)Helper function to pop max value from max-heap maintaining heap property

while (i < n && projects[i][0] <= W)Add all projects affordable with current capital to max-profit heap

heapPush(maxProfitHeap, projects[i][1]);Push profit into max-heap

if (maxProfitHeap.length === 0) break;If no projects affordable, break early to save time

W += heapPop(maxProfitHeap);Pick project with max profit and add to capital

⏱

Complexity

TimeO(n log n + K log n)

SpaceO(n)

Sorting takes O(n log n). Each project is pushed and popped at most once from heaps, each operation O(log n).

💡 For n=100000 and K=100000, this approach is efficient enough to run within seconds.

Interview Verdict: Accepted

This is the optimal approach commonly expected in interviews for this problem.

🧠

Optimized Two Heaps with Early Stopping

💡 This approach is a slight optimization of the previous by stopping early if no projects are affordable, saving unnecessary iterations.

Intuition

If at any iteration no projects can be started, we can stop immediately since capital won't increase further.

Algorithm

1. Sort projects by capital ascending.
2. Use two heaps: min-heap for capital and max-heap for profits.
3. For each iteration up to K:
4. Move all projects affordable with current capital from min-heap to max-heap.
5. If max-heap is empty, break early.
6. Pop max profit project and add profit to capital.
7. Return final capital.

💡 This approach is similar to the previous but explicitly uses a min-heap for capital to efficiently find affordable projects.

</>

Code

import heapq

def findMaxCapital(K, W, Profits, Capital):
    n = len(Profits)
    min_capital_heap = []
    max_profit_heap = []

    for c, p in zip(Capital, Profits):
        heapq.heappush(min_capital_heap, (c, p))

    for _ in range(K):
        while min_capital_heap and min_capital_heap[0][0] <= W:
            c, p = heapq.heappop(min_capital_heap)
            heapq.heappush(max_profit_heap, -p)
        if not max_profit_heap:
            break
        W += -heapq.heappop(max_profit_heap)
    return W

# Driver code
if __name__ == '__main__':
    K = 2
    W = 0
    Profits = [1, 2, 3]
    Capital = [0, 1, 1]
    print(findMaxCapital(K, W, Profits, Capital))  # Output: 4

Line Notes

min_capital_heap = []Min-heap to store projects by capital requirement for efficient retrieval

for c, p in zip(Capital, Profits):Push all projects into min-heap keyed by capital

while min_capital_heap and min_capital_heap[0][0] <= W:Move all projects affordable with current capital to max-profit heap

heapq.heappush(max_profit_heap, -p)Push negative profit to simulate max-heap using min-heap

if not max_profit_heap:If no projects affordable, break early to save time

W += -heapq.heappop(max_profit_heap)Pick project with max profit and add to capital

import java.util.*;
public class IPOOptimizedTwoHeaps {
    public static int findMaxCapital(int K, int W, int[] Profits, int[] Capital) {
        int n = Profits.length;
        PriorityQueue<int[]> minCapitalHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < n; i++) {
            minCapitalHeap.offer(new int[]{Capital[i], Profits[i]});
        }

        for (int k = 0; k < K; k++) {
            while (!minCapitalHeap.isEmpty() && minCapitalHeap.peek()[0] <= W) {
                maxProfitHeap.offer(minCapitalHeap.poll()[1]);
            }
            if (maxProfitHeap.isEmpty()) break;
            W += maxProfitHeap.poll();
        }
        return W;
    }

    public static void main(String[] args) {
        int K = 2;
        int W = 0;
        int[] Profits = {1, 2, 3};
        int[] Capital = {0, 1, 1};
        System.out.println(findMaxCapital(K, W, Profits, Capital)); // Output: 4
    }
}

Line Notes

PriorityQueue<int[]> minCapitalHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));Min-heap for projects keyed by capital requirement

PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>(Collections.reverseOrder());Max-heap for profits to pick most profitable projects

minCapitalHeap.offer(new int[]{Capital[i], Profits[i]});Add all projects to min-heap

while (!minCapitalHeap.isEmpty() && minCapitalHeap.peek()[0] <= W)Move all affordable projects to max-profit heap

if (maxProfitHeap.isEmpty()) break;If no projects affordable, break early

W += maxProfitHeap.poll();Pick project with max profit and add to capital

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int findMaxCapital(int K, int W, vector<int>& Profits, vector<int>& Capital) {
    int n = Profits.size();
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minCapitalHeap;
    priority_queue<int> maxProfitHeap;

    for (int i = 0; i < n; i++) {
        minCapitalHeap.emplace(Capital[i], Profits[i]);
    }

    for (int k = 0; k < K; k++) {
        while (!minCapitalHeap.empty() && minCapitalHeap.top().first <= W) {
            maxProfitHeap.push(minCapitalHeap.top().second);
            minCapitalHeap.pop();
        }
        if (maxProfitHeap.empty()) break;
        W += maxProfitHeap.top();
        maxProfitHeap.pop();
    }
    return W;
}

int main() {
    int K = 2;
    int W = 0;
    vector<int> Profits = {1, 2, 3};
    vector<int> Capital = {0, 1, 1};
    cout << findMaxCapital(K, W, Profits, Capital) << endl; // Output: 4
    return 0;
}

Line Notes

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minCapitalHeap;Min-heap for projects keyed by capital requirement

priority_queue<int> maxProfitHeap;Max-heap for profits to pick most profitable projects

minCapitalHeap.emplace(Capital[i], Profits[i]);Add all projects to min-heap

while (!minCapitalHeap.empty() && minCapitalHeap.top().first <= W)Move all affordable projects to max-profit heap

if (maxProfitHeap.empty()) break;If no projects affordable, break early

W += maxProfitHeap.top();Pick project with max profit and add to capital

maxProfitHeap.pop();Remove chosen project from heap

function findMaxCapital(K, W, Profits, Capital) {
    const n = Profits.length;
    const minCapitalHeap = [];
    const maxProfitHeap = [];

    function minHeapPush(heap, val) {
        heap.push(val);
        let i = heap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (heap[parent][0] <= heap[i][0]) break;
            [heap[parent], heap[i]] = [heap[i], heap[parent]];
            i = parent;
        }
    }

    function minHeapPop(heap) {
        const top = heap[0];
        const end = heap.pop();
        if (heap.length > 0) {
            heap[0] = end;
            let i = 0;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
                if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
                if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
                if (smallest === i) break;
                [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
                i = smallest;
            }
        }
        return top;
    }

    function maxHeapPush(heap, val) {
        heap.push(val);
        let i = heap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (heap[parent] >= heap[i]) break;
            [heap[parent], heap[i]] = [heap[i], heap[parent]];
            i = parent;
        }
    }

    function maxHeapPop(heap) {
        const top = heap[0];
        const end = heap.pop();
        if (heap.length > 0) {
            heap[0] = end;
            let i = 0;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, largest = i;
                if (left < heap.length && heap[left] > heap[largest]) largest = left;
                if (right < heap.length && heap[right] > heap[largest]) largest = right;
                if (largest === i) break;
                [heap[i], heap[largest]] = [heap[largest], heap[i]];
                i = largest;
            }
        }
        return top;
    }

    for (let i = 0; i < n; i++) {
        minHeapPush(minCapitalHeap, [Capital[i], Profits[i]]);
    }

    for (let k = 0; k < K; k++) {
        while (minCapitalHeap.length > 0 && minCapitalHeap[0][0] <= W) {
            const [c, p] = minHeapPop(minCapitalHeap);
            maxHeapPush(maxProfitHeap, p);
        }
        if (maxProfitHeap.length === 0) break;
        W += maxHeapPop(maxProfitHeap);
    }
    return W;
}

// Test
console.log(findMaxCapital(2, 0, [1, 2, 3], [0, 1, 1])); // Output: 4

Line Notes

function minHeapPush(heap, val)Push value into min-heap keyed by capital maintaining heap property

function minHeapPop(heap)Pop smallest capital project from min-heap maintaining heap property

function maxHeapPush(heap, val)Push value into max-heap keyed by profit maintaining heap property

function maxHeapPop(heap)Pop largest profit project from max-heap maintaining heap property

minHeapPush(minCapitalHeap, [Capital[i], Profits[i]]);Add all projects to min-heap keyed by capital

while (minCapitalHeap.length > 0 && minCapitalHeap[0][0] <= W)Move all affordable projects to max-profit heap

if (maxProfitHeap.length === 0) break;If no projects affordable, break early

W += maxHeapPop(maxProfitHeap);Pick project with max profit and add to capital

⏱

Complexity

TimeO(n log n + K log n)

SpaceO(n)

Similar to previous approach but uses explicit min-heap for capital to efficiently find affordable projects.

💡 This approach is optimal and slightly more explicit in managing projects by capital.

Interview Verdict: Accepted

This is a clean and efficient solution suitable for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the two heaps approach (Approach 2 or 3) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^K)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Sorting + Two Heaps	O(n log n + K log n)	O(n)	No	N/A	Code this approach
3. Optimized Two Heaps with Early Stopping	O(n log n + K log n)	O(n)	No	N/A	Code this approach or mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the optimized two heaps approach as the best solution. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem constraints and inputs.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce sorting and two heaps to optimize project selection.Step 4: Code the two heaps solution carefully.Step 5: Test with sample and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

The interviewer tests your ability to handle greedy optimization, use appropriate data structures (heaps), and write clean, efficient code under constraints.

Common Follow-ups

• What if projects can be done in parallel? → Use a priority queue with concurrency constraints.
• How to handle very large K? → Early stopping when no projects are affordable.

💡 These follow-ups test your understanding of problem variations and ability to adapt your solution.

🔍

Pattern Recognition

When to Use

1) You have a list of tasks/projects with constraints on starting them (capital). 2) You want to maximize a value (profit/capital) after limited picks. 3) You must pick projects you can afford at each step. 4) Efficient selection requires dynamic availability management.

Signature Phrases

maximum capital after at most K projectsminimum capital required to startpick projects you can afford

NOT This Pattern When

Knapsack DP problems - those require different DP-based approaches, not greedy two heaps.

Similar Problems

Maximum Profit in Job Scheduling - scheduling with profits and constraintsTask Scheduler - managing tasks with constraints and priorities

Practice

1. Given the following Python code for computing sliding window medians, what is the output when nums = [1, 3, -1] and k = 3?

easy

A. [1.0]

B. [1.0, 3.0]

C. [1.0, -1.0]

D. [3.0]

Solution

1. Step 1: Initialize window and compute median

   Window = [1, 3, -1] sorted -> [-1, 1, 3], median at index 1 (k//2) is 1.0

2. Step 2: Loop from i=k to len(nums)

   Since len(nums) = 3 and k=3, loop does not run, so only one median computed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one window median computed [OK]

Hint: No sliding when window size equals array length [OK]

Common Mistakes:

• Assuming loop runs even when window covers entire array
• Misindexing median for odd k
• Returning multiple medians incorrectly

2. You are given a list of intervals, each with a start and end time. For each interval, you want to find the interval with the smallest start time that is greater than or equal to the end time of the current interval. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use two max-heaps: one for interval starts and one for interval ends, to efficiently find the next interval.

B. Use a greedy algorithm that picks the earliest finishing interval first.

C. Sort intervals by start time and use dynamic programming to find the next interval.

D. Use a brute force nested loop to compare each interval with every other interval.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding, for each interval, the next interval with the smallest start time ≥ current interval's end time.

2. Step 2: Evaluate approaches

   Brute force (nested loops) is correct but inefficient (O(n²)). Sorting + binary search is efficient but requires extra steps. The two max-heaps approach efficiently tracks max starts and ends to find next intervals in O(n log n) time, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps approach matches the problem's need for efficient next interval lookup [OK]

Hint: Two heaps efficiently track max starts and ends [OK]

Common Mistakes:

• Assuming greedy earliest finish works
• Using DP unnecessarily
• Brute force accepted as optimal

3. You need to rearrange characters in a string so that the same character appears at least k distance apart. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Greedy approach using a max heap to always pick the most frequent character and a fixed-size queue to enforce the k-distance constraint

B. Sorting characters by frequency and placing them in a round-robin fashion without additional data structures

C. Dynamic programming to build solutions by storing subproblems of partial rearrangements

D. Backtracking with pruning to try all permutations until a valid one is found

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging characters so that identical characters are at least k apart, which is a scheduling constraint.

2. Step 2: Identify approach that enforces frequency and spacing

   Greedy with a max heap picks the most frequent character available, and a fixed-size queue enforces the cooldown period (k-distance), ensuring no character is reused too soon.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap + fixed-size queue is the known optimal pattern [OK]

Hint: Max heap + fixed-size queue enforces k-distance [OK]

Common Mistakes:

• Assuming backtracking is efficient enough for large inputs
• Believing DP can directly solve this without exponential states
• Thinking simple sorting suffices without enforcing cooldown

4. Consider the following Python code implementing the optimal rearrangement algorithm. What is the output of rearrangeString("aabc", 2)?

easy

A. "abac"

B. "abca"

C. "aabc"

D. "" (empty string)

Solution

1. Step 1: Trace first iterations of the loop

   Initial freq: {a:2, b:1, c:1}, max_heap=[(-2,'a'),(-1,'b'),(-1,'c')]. Pop 'a', res=['a'], queue=[('a',-1)]. Queue size < k=2, continue.

2. Step 2: Next iterations and final string

   Pop 'b', res=['a','b'], queue=[('a',-1),('b',0)]. Queue size == k, pop front ('a',-1), since count<0, push back (-1,'a'). Next pop 'a', res=['a','b','a'], queue=[('b',0),('a',0)]. Pop front ('b',0), count not <0, no push. Pop 'c', res=['a','b','a','c'], queue=[('a',0),('c',0)]. Final string length matches input length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output "abac" respects k=2 spacing and uses all chars [OK]

Hint: Track heap pops and queue size carefully [OK]

Common Mistakes:

• Confusing when to push back characters into heap
• Off-by-one in decrementing counts
• Returning partial strings without length check

5. What is the time complexity of the optimal greedy algorithm that uses a max heap and a fixed-size queue to rearrange a string of length n with m unique characters and distance constraint k?

medium

A. O(n log m) because each character is pushed and popped from a heap of size up to m

B. O(n * k) because each character is processed with a queue of size k

C. O(n^2) because the algorithm may scan the string multiple times to enforce constraints

D. O(m log n) because the heap operations depend on string length n

Solution

1. Step 1: Identify main operations

   Each character is pushed and popped from a max heap of size up to m (number of unique chars), each heap operation costs O(log m).

2. Step 2: Count total operations

   Since total characters are n, total heap operations are O(n), resulting in O(n log m) time complexity. However, the queue operations to enforce the k-distance constraint can cause up to O(n * k) complexity in the worst case because each character waits in the cooldown queue for k steps.

3. Step 3: Choose the tightest upper bound

   Considering the cooldown queue of size k, the overall complexity is O(n * k).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue operations dominate due to cooldown size k [OK]

Hint: Cooldown queue size k affects complexity [OK]

Common Mistakes:

• Ignoring cooldown queue impact
• Assuming heap operations dominate always
• Mixing up m and n in heap operation costs