I am trying to optimize this as best as I can. Here are two possible solutions I have developed and their respective time and space complexity.
Can you please let me know if my time/space complexity is correct, and if there is a more optimized solution?
There are a list of product stocks (4, 5, 3) which means there are 3
products, item 1 has 4 in stock, item 2 has 5 in stock, and item 3 has
3 in stock.
The profit on a single sale is the number of items left. When we make
a sale, we decrease the stock for that particular item.
For example, if we sell item 2, we make a profit of 5. The next time
we sell item 2, we make a profit of 4. Next time is 3.
We are told how many orders we can make, and we need to maximize the
profit within that order amount.
Example: items: (3, 4) orders: 6
Explanation: Prices are (4, 3, 2, 1) and (3, 2, 1). We sell
Python Heap solution. Time complexity: O(nlog(n)), Space complexity: O(n)
import heapq def highestProfit(numSuppliers, inventory, order): def pushHeap(heap, value): heapq.heappush(heap, -1 * value) def popHeap(heap): return -1 * heapq.heappop(heap) heap = () for i in inventory: pushHeap(heap, i) profit = 0 while (order > 0): maxPrice = popHeap(heap) profit += maxPrice if (maxPrice - 1 != 0): pushHeap(heap, maxPrice - 1) order -= 1 return profit
Non heap solution. Time complexity: O(n), Space complexity: O(n)
def highestProfitSimplified(numSuppliers, inventory, order): maxInv = max(inventory) arr = (0) * (maxInv + 1) for i in inventory: arr(i) += 1 print(arr) profit = 0 while (maxInv >= 1 and order > 0): profit += min(arr(maxInv), order) * maxInv arr(maxInv - 1) += arr(maxInv) order -= arr(maxInv) maxInv -= 1 return profit