IPO (Maximize Capital, K Projects)

▶

Steps

setup

Initialize min-heap with all projects by capital

All projects are pushed into a min-heap keyed by their capital requirement. This organizes projects so the cheapest capital projects are accessible first.

💡 Sorting projects by capital upfront allows efficient retrieval of affordable projects as capital grows.

Line:

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

💡 Projects are now sorted implicitly in a min-heap by capital, ready for incremental affordability checks.

traverse

Start first iteration: K=1, current capital W=0

Begin the first iteration to select one project. Current capital is 0, so we check which projects are affordable.

💡 Each iteration attempts to pick the most profitable project affordable with current capital.

Line:

for _ in range(K):

💡 We are ready to move projects affordable with W=0 from min-heap to max-heap.

insert

Move affordable projects (capital <= 0) to max-profit heap

Project with capital 0 and profit 1 is affordable. It is popped from min-heap and pushed into max-heap as -profit for max-heap behavior.

💡 Moving affordable projects to max-heap allows quick access to the most profitable projects we can currently afford.

Line:

while min_capital_heap and min_capital_heap[0][0] <= W:
    c, p = heapq.heappop(min_capital_heap)
    heapq.heappush(max_profit_heap, -p)

💡 Only projects affordable with current capital are considered for profit selection.

compare

No more affordable projects to move this iteration

Next project in min-heap requires capital 1, which is greater than current capital 0, so stop moving projects.

💡 Stopping here ensures only truly affordable projects are considered this iteration.

Line:

while min_capital_heap and min_capital_heap[0][0] <= W:

💡 Capital constraint strictly limits which projects can be considered each iteration.

extract_max

Pop max profit project from max-heap and add to capital

Pop the project with max profit (1) from max-heap and add it to current capital W=0, updating W to 1.

💡 Selecting the most profitable affordable project maximizes capital growth each iteration.

Line:

W += -heapq.heappop(max_profit_heap)

💡 Capital increases, enabling more projects to become affordable next iteration.

traverse

Start second iteration: K=2, current capital W=1

Begin second iteration with updated capital 1, checking which projects are now affordable.

💡 Capital growth allows more projects to be considered for selection.

Line:

for _ in range(K):

💡 We will move all projects with capital <= 1 to max-heap.

insert

Move first affordable project (1,2) to max-profit heap

Project with capital 1 and profit 2 is affordable. It is popped from min-heap and pushed into max-heap as -2.

💡 Adding all affordable projects to max-heap ensures we pick the most profitable next.

Line:

while min_capital_heap and min_capital_heap[0][0] <= W:
    c, p = heapq.heappop(min_capital_heap)
    heapq.heappush(max_profit_heap, -p)

💡 Max-heap now contains profit -2.

insert

Move second affordable project (1,3) to max-profit heap

Project with capital 1 and profit 3 is also affordable. It is popped from min-heap and pushed into max-heap as -3.

💡 Multiple projects can become affordable simultaneously and compete for selection.

Line:

while min_capital_heap and min_capital_heap[0][0] <= W:
    c, p = heapq.heappop(min_capital_heap)
    heapq.heappush(max_profit_heap, -p)

💡 Max-heap now contains profits -3 and -2, with -3 at root (max profit).

compare

No more affordable projects to move this iteration

Min-heap is now empty, so no more projects to move to max-heap.

💡 All affordable projects have been moved, ready for profit selection.

Line:

while min_capital_heap and min_capital_heap[0][0] <= W:

💡 Capital constraint fully applied this iteration.

extract_max

Pop max profit project (3) from max-heap and add to capital

Pop the project with max profit 3 from max-heap and add it to capital W=1, updating W to 4.

💡 Selecting the highest profit project maximizes capital growth and final answer.

Line:

W += -heapq.heappop(max_profit_heap)

💡 Capital is maximized after K projects are selected.

prune

End of iterations, return final capital

All K=2 projects have been selected. The algorithm returns the final capital W=4 as the answer.

💡 The final capital reflects the maximum achievable after selecting up to K projects.

Line:

return W

💡 The algorithm terminates with the optimal capital value.

import heapq

def findMaxCapital(K, W, Profits, Capital):
    n = len(Profits)
    min_capital_heap = []  # STEP 1: Initialize min-heap
    max_profit_heap = []

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

    for _ in range(K):  # STEP 2, 6, 9, 11
        while min_capital_heap and min_capital_heap[0][0] <= W:  # STEP 3,7,8
            c, p = heapq.heappop(min_capital_heap)
            heapq.heappush(max_profit_heap, -p)
        if not max_profit_heap:  # STEP 4, 10
            break
        W += -heapq.heappop(max_profit_heap)  # STEP 5, 10
    return W

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

📊

IPO (Maximize Capital, K Projects) - Watch the Algorithm Execute, Step by Step

Watching each heap operation and decision reveals how the algorithm efficiently picks the best projects within capital constraints, which is hard to grasp from code alone.

insertmin-heap

(0,1)

0

(1,2)

1

(1,3)

2

peekmin-heap

(0,1)

0

(1,2)

1

(1,3)

2

insertmax-heap

-1

0

peekmin-heap

(1,2)

0

(1,3)

1

extract_maxmax-heap

empty heap

Added: 1

peekmin-heap

(1,2)

0

(1,3)

1

insertmax-heap

-2

0

heapify_upmax-heapswap [1↔0]

-3

0

-2

1

peekmin-heap

empty heap

extract_maxmax-heap

-2

0

Added: 3

peekmax-heap

-2

0

Added: 4

Key Takeaways

✓ Using two heaps allows efficient filtering and selection of projects by capital and profit constraints.

This insight is hard to see from code alone because the interplay of two heaps is subtle and dynamic.

✓ Capital growth unlocks more projects, which are then pushed into the max-heap for profit selection.

Watching the heaps evolve step-by-step clarifies how capital constraints gate project availability.

✓ Early stopping occurs if no projects are affordable, preventing unnecessary iterations.

Seeing the break condition in action helps understand algorithm efficiency.

Practice

1. Given the following code snippet for finding employee free time, what is the final output when the input schedule is [[[1,2],[5,6]], [[1,3]], [[4,10]]]?

from typing import List

def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
    intervals = [iv for employee in schedule for iv in employee]
    intervals.sort(key=lambda x: x[0])
    free_times = []
    prev_end = intervals[0][1]
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start > prev_end:
            free_times.append([prev_end, start])
        prev_end = max(prev_end, end)
    return free_times

schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
print(employeeFreeTime(schedule))

easy

A. [[3,4]]

B. [[3,4], [6,10]]

C. [[2,4]]

D. [[3,4]]

Solution

1. Step 1: Sort all intervals

   Flattened intervals: [1,2], [5,6], [1,3], [4,10]. Sorted by start: [1,2], [1,3], [4,10], [5,6].

2. Step 2: Merge intervals and find gaps

   Initialize prev_end=2. Iterate: - Interval [1,3]: start=1 ≤ prev_end=2, update prev_end=max(2,3)=3 - Interval [4,10]: start=4 > prev_end=3, gap [3,4] added, update prev_end=10 - Interval [5,6]: start=5 ≤ prev_end=10, update prev_end=max(10,6)=10 Return free_times=[[3,4]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only one gap between merged intervals is [3,4] [OK]

Hint: Sort intervals and track max end to find gaps [OK]

Common Mistakes:

• Off-by-one errors in gap detection
• Including zero-length intervals
• Incorrect sorting leading to wrong gaps

2. You need to continuously receive numbers from a stream and efficiently find the median after each insertion. Which approach guarantees an optimal solution with O(log n) insertion and O(1) median retrieval?

easy

A. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, balancing their sizes.

B. Sort the entire list after each insertion and pick the middle element(s).

C. Use a balanced binary search tree to insert and find median in O(log n) time.

D. Use a single min-heap to store all elements and extract median by popping half the elements.

Solution

1. Step 1: Understand the problem constraints

   The problem requires efficient insertion and median retrieval from a data stream.

2. Step 2: Evaluate approaches

   Sorting after each insertion is O(n log n), too slow. A balanced BST can do insertions in O(log n) but median retrieval is not O(1). Using a single min-heap cannot separate lower and upper halves, so median calculation is incorrect. Maintaining two heaps (max-heap for lower half, min-heap for upper half) allows O(log n) insertion and O(1) median retrieval by balancing sizes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps balance halves for median -> [OK]

Hint: Two heaps balance halves for median retrieval [OK]

Common Mistakes:

• Sorting entire list each time is too slow
• Using one heap cannot separate halves
• Assuming balanced BST gives O(1) median retrieval

3. 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

4. Identify the bug in the following code snippet for computing maximum team performance:

import heapq

MOD = 10**9 + 7

def maxPerformance(n, speed, efficiency, k):
    engineers = sorted(zip(efficiency, speed), key=lambda x: -x[0])
    max_perf = 0
    speed_heap = []
    sum_speed = 0
    for eff, spd in engineers:
        heapq.heappush(speed_heap, spd)
        # Missing sum_speed update when popping
        if len(speed_heap) > k:
            heapq.heappop(speed_heap)
        sum_speed += spd
        max_perf = max(max_perf, sum_speed * eff)
    return max_perf % MOD

medium

A. Line where sum_speed is incremented by spd after pushing to heap

B. Line where engineers are sorted by efficiency descending

C. Line where heapq.heappop is called without updating sum_speed

D. Line where max_perf is updated with sum_speed * eff

Solution

1. Step 1: Identify heap pop operation

   When the heap size exceeds k, the smallest speed is popped but sum_speed is not decremented accordingly.

2. Step 2: Understand impact on sum_speed

   Not updating sum_speed causes it to include speeds no longer in the team, leading to incorrect performance calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   sum_speed must be updated when removing speed from heap [OK]

Hint: Check if sum_speed changes when popping from heap [OK]

Common Mistakes:

• Forgetting to update sum_speed on pop
• Sorting by wrong key
• Updating max_perf before sum_speed is correct

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