Best Time to Buy and Sell Stock
Explore how to maximize profit by selecting the best days to buy and sell stocks using greedy techniques. Understand the problem constraints and develop an optimal linear time and constant space solution. This lesson helps you apply practical coding patterns to solve common interview questions efficiently.
We'll cover the following...
Statement
Given an array, prices, where prices[i] represent the price of a stock on the i-th day, maximize profit by selecting a single day to buy the stock and a different day in the future to sell it.
Return the maximum profit that can be achieved from this transaction. If no profit can be made, return 0.
Constraints:
We can’t sell before buying a stock, that is, the array index at which stock is bought will always be less than the index at which the stock is sold.
prices.lengthprices[i]
Examples
Understand the problem
Let's take a moment to make sure that you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Best Time to Buy and Sell Stock
What should be the output if the following prices are given as an input?
prices = [10, 4, 11, 1, 5]
9
7
1
3
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Note: As an additional challenge, we have intentionally hidden the solution to this puzzle.
Try it yourself
Implement your solution in the following coding playground.
We have left the solution to this challenge as an exercise for you. The optimal solution to this problem runs in O(n) time and takes O(1) space. You may try to translate the logic of the solved puzzle into a coded solution.
def max_profit(prices):# Replace this placeholder return statement with your codereturn -1