Given stock prices for the next n days, how can you maximize your profit by buying or selling one share per day?
Medium
Buy and Sell Stock — Medium Maximize Stock Trading Profit. You are given a sequence of stock prices representing the value of a particular stock on consecutive days. You can complete as many transactions as you like with the following constraints:
You must buy before you sell. You cannot buy on one day and sell on the same day (buying and selling on the same day counts as nothing).
Maximize your profit given these conditions. For example, consider the following stock prices over a week: 1, 2, 3, 4, 5. If you buy on day 1 and sell on day 5, your profit will be 4 (buy at 1 and sell at 5).
Examples
stock_prices = [7, 1, 5, 3, 8, 6] output: 9 (Buy on day 2 at 1 and sell on day 3 at 5, buy on day 4 at 3 and sell on day 5 at 8) stock_prices = [1, 2, 3, 4, 5] output: 4 (Buy on day 1 at 1 and sell on day 5 at 5) stock_prices = [7, 6, 4, 3, 1] output: 0 (No transaction is done, i.e., max profit = 0) stock_prices = [1, 10, 2, 3] output: 10 (Buy on day 1 at 1 and sell on day 2 at 10, buy on day 3 at 2 and sell on day 4 at 3) stock_prices = [10, 1, 5, 8, 7, 12] output: 11 (Buy on day 2 at 1 and sell on day 6 at 12)
The goal of this solution is to maximize profit by buying and selling stocks on different days, given an array of stock prices where each element represents the price of the stock on a particular day.
The algorithm uses a greedy approach with a min-heap (implemented as a priority queue) to keep track of the lowest prices encountered so far. By maintaining a collection of potential buy prices, we can ensure that we always buy at the lowest possible price and sell at a higher price later, thereby maximizing profit.
Here's a step-by-step explanation of the approach:
-
Initialize Data Structures: Use a priority queue (
options) to act as a min-heap to store the prices of stocks. InitializecurrentProfitto 0, which will store the accumulated profit. -
Iterate Through the Stock Prices: For each price in the
stockPricesarray:- If the current price is higher than the lowest price in the heap (
options.peek()), compute the profit by selling at the current price and buying at the lowest price. UpdatecurrentProfitaccordingly. - Remove the lowest price from the heap after using it for profit calculation.
- Push the current price into the heap as a potential buy price.
- If the current price is higher than the lowest price in the heap (
-
Return the Total Profit: After iterating through all the prices, return the accumulated
currentProfit.
This approach ensures that we always buy low and sell high, using the min-heap to efficiently manage and access the lowest prices encountered.
Time Complexity: Inserting a price into the min-heap and removing the smallest price both take O(log n) time, where n is the number of elements in the heap. Since we perform these operations for each of the n prices in the stockPrices array, the overall time complexity is O(n log n).
Space Complexity: The space complexity is dominated by the storage required for the heap. In the worst case, we might store all n prices in the heap, leading to a space complexity of O(n).
More optimized approach
- Iterate Through the Stock Prices: Starting from day 2, compare each price to the previous day's price. If today's price is higher than yesterday's, add the difference to the profit.
- Return the Total Profit: After iterating through all the prices, return the accumulated profit.
Time Complexity: O(n). A single pass through the array, where n is the number of stock prices.
Space Complexity: O(1). No auxiliary data structures are used.
In this video, Lewin (Dropbox SWE) answers an interview question about the best times to buy and sell stock.
Interview experiences
1 sharedRelated courses
