LeetCode 502: IPO Solution

Master LeetCode problem 502 (IPO), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

502. IPO

Hard

Array Greedy Sorting Heap (Priority Queue)

Problem Explanation

Explanation

To maximize the final capital after finishing at most k distinct projects, we can follow the following approach:

Create a list of projects sorted by their capital requirements.
Maintain a priority queue (max heap) to store the profits of the available projects.
Iterate k times:
- While iterating, check if any project's capital requirement is less than or equal to the current capital. If so, add its profit to the priority queue.
- Select the project with the maximum profit from the priority queue and update the current capital.
Repeat the above step k times to select the best k projects to maximize the final capital.

Time Complexity: O(nlogn + klogn) where n is the number of projects
Space Complexity: O(n)

Solution Code

import java.util.*;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<int[]> pqCapital = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pqProfit = new PriorityQueue<>((a, b) -> b - a);

        int n = profits.length;
        int currCapital = w;

        for (int i = 0; i < n; i++) {
            pqCapital.offer(new int[]{capital[i], profits[i]});
        }

        for (int i = 0; i < k; i++) {
            while (!pqCapital.isEmpty() && pqCapital.peek()[0] <= currCapital) {
                pqProfit.offer(pqCapital.poll()[1]);
            }

            if (pqProfit.isEmpty()) {
                break;
            }

            currCapital += pqProfit.poll();
        }

        return currCapital;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 502 (IPO)?

This page provides optimized solutions for LeetCode problem 502 (IPO) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 502 (IPO)?

The time complexity for LeetCode 502 (IPO) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 502 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 502 in Java, C++, or Python.

Back to LeetCode Solutions