What is the brute force approach and complexity for IPO?

Each round, check every unused project for the largest profit you can afford with time complexity O(K · N) and space complexity O(N).

What is the optimal approach and complexity for IPO?

Sort by capital; each round push the newly affordable profits, then pop the largest with optimal time complexity O(N log N + K log N) and space complexity O(N).

How do you identify the pattern for IPO?

Look for key signals in the prompt: "minimum capital needed" indicates Each project unlocks when capital reaches a threshold, so a list sorted by capital with one pointer tracks what is unlocked.; "at most k projects, maximize the final capital" indicates Each round picks one project, and the best pick is the largest affordable profit: a max-heap.; "the profit is added to your capital" indicates Capital only grows, so a project that is affordable stays affordable..

IPO

Hard·LeetCode #502 Pro OnlyInterview-Level

LeetCode

Problem Statement

You can finish at most k projects, one after another, and each project at most once. Project i pays a profit of profits[i]. To start project i you need at least capital[i] capital. You start with w capital, and finishing a project adds its profit to your capital.

Choose the projects so that your final capital is as large as possible, and return that capital.

The answer always fits in a 32-bit signed integer.

Input

k, the most projects you may finish, and w, your starting capital. Then profits and capital, two arrays of the same length.

Output

The largest final capital you can reach.

Example 1

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

Output: 4

With 0 capital only project 0 (needs 0) can start. Finish it and your capital is 1. Projects 1 and 2 both need 1, so both are open. Project 2 pays 3, so do it: 1 + 3 = 4. That is two projects, the limit.

Example 2

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

Output: 6

Project 0 first: capital 1. Then project 1 (needs 1) pays 2, so capital 3. Then project 2 (needs 2) pays 3, so capital 6.

Constraints

• 1 ≤ k ≤ 10^5
• 0 ≤ w ≤ 10^9
• n == profits.length
• n == capital.length
• 1 ≤ n ≤ 10^5
• 0 ≤ profits[i] ≤ 10^4
• 0 ≤ capital[i] ≤ 10^9

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum capital needed”

→ Each project unlocks when capital reaches a threshold, so a list sorted by capital with one pointer tracks what is unlocked.

“at most k projects, maximize the final capital”

→ Each round picks one project, and the best pick is the largest affordable profit: a max-heap.

“the profit is added to your capital”

→ Capital only grows, so a project that is affordable stays affordable.

Approach Complexity Ladder

Brute Force — scan all projects every roundO(K · N)O(N)

Each round, check every unused project for the largest profit you can afford

Optimal — sort by capital, max-heap of affordable profitsO(N log N + K log N)O(N)

Sort by capital; each round push the newly affordable profits, then pop the largest

Brute Force Intuition

In each round, scan all unused projects and take the largest profit whose capital is at most your current capital. Add that profit to your capital, mark the project as used, and repeat k times. Stop early if no project is affordable.

Recognition rule for this sub-pattern:

One heap holds what you can use now, the other what unlocks later. Move items across as conditions change.

Remember this · Two Heaps

Trigger

Running median, sliding median, choosing from two pools (available vs locked).

Think

Can I split the data into two halves and only care about the boundary between them?

Key question

How do I rebalance so the sizes differ by at most one?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Heaps translate into production architectures and low-level memory mechanics.

LLD Architecture

Real-time Metrics & Rolling Percentiles

Calculating streaming median and P99 latency in production telemetry systems.

Explore Track

C++ Internals

Smart Pointers & Ownership Semantics

Managing node ownership without memory leaks across priority queues.

Explore Track

Total Cost to Hire K Workers