IPO - Practice Coding Problems

IPO - Problem

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 i-th 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. Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Start with capital 0. Can afford project 0 (capital=0, profit=1). After project 0, capital becomes 1. Now can afford projects 1 or 2. Project 1 has profit=2, so pick it. Final capital: 0 + 1 + 2 = 3. Wait, let me recalculate: we can do project 0 (capital 0→1), then project 2 (capital 1→4). Actually both projects 1 and 2 need capital 1, and both give different profits. Project 2 gives profit 3, so final is 0→1→4.

Example 2 — Limited by k

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

› Output: 6

💡 Note: Can do all projects in order: project 0 (0→1), then project 1 (1→3), then project 2 (3→6)

Example 3 — Limited by Capital

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

› Output: 0

💡 Note: Cannot afford any project since all require capital ≥ 1 but we start with 0

Constraints

1 ≤ k ≤ 10⁵
0 ≤ w ≤ 10⁹
n == profits.length == capital.length
1 ≤ n ≤ 10⁵
0 ≤ profits[i] ≤ 10⁴
0 ≤ capital[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

k=2 projects max, w=0 starting capital, projects with capital/profit requirements

Process

Greedily select most profitable projects we can afford

Output

Maximum achievable capital after k projects

Key Takeaway

🎯 Key Insight: Use heaps to efficiently track and select the most profitable projects you can afford at each step

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use a greedy approach with heaps: sort projects by capital requirement, then always pick the most profitable project you can currently afford. Best approach uses two heaps for O(n log n + k log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Two Heaps	O(n log n + k log n)	O(n)	Use min-heap for available projects and max-heap for profits to greedily select optimal projects
Brute Force - Try All Combinations	O(n^k * k)	O(k)	Generate all possible combinations of k projects and find the one with maximum profit

Greedy with Two Heaps — Algorithm Steps

Sort projects by capital requirement
Use min-heap to track projects by capital
Use max-heap to find most profitable available project
Repeat k times: make projects available, pick best one

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Capital

Order projects by minimum capital required

Heap Operations

Add affordable projects to max-heap, extract most profitable

Repeat k Times

Continue until k projects completed or no more affordable

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int cap, prof;
} Project;

typedef struct {
    int *heap;
    int size;
    int capacity;
} MaxHeap;

int compare(const void *a, const void *b) {
    return ((Project*)a)->cap - ((Project*)b)->cap;
}

MaxHeap* createMaxHeap(int capacity) {
    MaxHeap* h = (MaxHeap*)malloc(sizeof(MaxHeap));
    h->heap = (int*)malloc(capacity * sizeof(int));
    h->size = 0;
    h->capacity = capacity;
    return h;
}

void maxHeapify(MaxHeap* h, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < h->size && h->heap[left] > h->heap[largest])
        largest = left;
    if (right < h->size && h->heap[right] > h->heap[largest])
        largest = right;
        
    if (largest != i) {
        int temp = h->heap[i];
        h->heap[i] = h->heap[largest];
        h->heap[largest] = temp;
        maxHeapify(h, largest);
    }
}

void heapPush(MaxHeap* h, int val) {
    h->heap[h->size] = val;
    int i = h->size++;
    
    while (i > 0 && h->heap[(i-1)/2] < h->heap[i]) {
        int temp = h->heap[i];
        h->heap[i] = h->heap[(i-1)/2];
        h->heap[(i-1)/2] = temp;
        i = (i-1)/2;
    }
}

int heapPop(MaxHeap* h) {
    if (h->size == 0) return -1;
    
    int max = h->heap[0];
    h->heap[0] = h->heap[--h->size];
    maxHeapify(h, 0);
    return max;
}

int solution(int k, int w, int profits[], int capital[], int n) {
    // Sort projects by capital requirement
    Project projects[n];
    for (int i = 0; i < n; i++) {
        projects[i].cap = capital[i];
        projects[i].prof = profits[i];
    }
    qsort(projects, n, sizeof(Project), compare);
    
    MaxHeap* available = createMaxHeap(n);
    int projectIdx = 0;
    int currentCapital = w;
    
    for (int i = 0; i < k; i++) {
        // Add all affordable projects to available heap
        while (projectIdx < n && projects[projectIdx].cap <= currentCapital) {
            heapPush(available, projects[projectIdx].prof);
            projectIdx++;
        }
        
        // If no projects available, break
        if (available->size == 0) {
            break;
        }
        
        // Pick the most profitable project
        int maxProfit = heapPop(available);
        currentCapital += maxProfit;
    }
    
    free(available->heap);
    free(available);
    return currentCapital;
}

int main() {
    int k, w;
    scanf("%d", &k);
    scanf("%d", &w);
    
    // Parse profits array
    char line[1000];
    scanf(" %[^\n]", line);
    int profits[100], profitCount = 0;
    char *token = strtok(line + 1, ",]"); // Skip '['
    while (token) {
        profits[profitCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse capital array
    scanf(" %[^\n]", line);
    int capital[100], capitalCount = 0;
    token = strtok(line + 1, ",]"); // Skip '['
    while (token) {
        capital[capitalCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(k, w, profits, capital, profitCount);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + k log n)

Sorting takes O(n log n), k iterations each with O(log n) heap operations

⚡ Linearithmic

Space Complexity

O(n)

Two heaps can store up to n projects total

⚡ Linearithmic Space

78.4K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Two Heaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler