< Back




502. IPO

We're trying to maximize LeetCode's capital so they can vie for an IPO. We've got a list of profits
with correlating capital it costs to undertake a project to receive said profit. Given k moves,
what's the maximum amount of capital we can accumulate?

This is a greedy problem, so first we'll have to couple the capital expenses and the profits, and
sort them by capital. As we complete projects, the amount we have in capital unlocks new projects,
so we'll have to use a pointer to our array to keep track of our frontier. For the projects that are
available to use, we'll use a max heap to select the most profitable one.

For k moves, we adjust our frontier to determine the list of our available projects based on
capital. For each project in the frontier, we push it into the max heap. We then pop from the max
heap and add the profit to our capital. If the heap is empty, we break the loop.

The solution is as follows:


  from heapq import heappush, heappop

  class Solution:
      def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
          heap, projects = [], list(zip(capital, profits))
          projects.sort()
          n, avail = len(projects), 0

          for _ in range(k):
              while avail < n and w >= projects[avail][0]:
                  heappush(heap, -projects[avail][1])
                  avail += 1

              if not heap:
                  return w

              w += -heappop(heap)

          return w


_ Time Complexity:

  O(n log(n)) - We have to sort the array.

_ Space Complexity:

  O(n) - We use a heap to store the projects.