Best Time to Buy and Sell Stock
EasyPrompt
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of buy and sell days to find the one that yields the maximum profit. We use nested loops to iterate through all valid transaction pairs.
Algorithm
- Initialize a variable
maxProfitto 0. - Iterate through the
pricesarray with an indexifrom 0 ton-2(representing the buy day). - Inside this loop, start another loop with an index
jfromi+1ton-1(representing the sell day). - Calculate the current profit:
profit = prices[j] - prices[i]. - Compare
profitwithmaxProfit. Ifprofitis greater, updatemaxProfit = profit. - After the loops complete, return
maxProfit.
Walkthrough
The brute force method systematically calculates the profit for every possible transaction. We assume we buy on day i and sell on a future day j (where j > i).
We use two nested loops. The outer loop iterates through each day i from the first to the second-to-last day, considering it as the potential buy day. The inner loop iterates through each subsequent day j from i+1 to the last day, considering it as the potential sell day.
For each pair of (buy_price, sell_price), we calculate the profit. We maintain a variable maxProfit which is updated whenever we find a profit greater than the current maxProfit.
If no profitable transaction can be made (i.e., prices are always decreasing), the maxProfit will remain at its initial value of 0.
class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { int profit = prices[j] - prices[i]; if (profit > maxProfit) { maxProfit = profit; } } } return maxProfit; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
Highly inefficient for large arrays.
Will result in a 'Time Limit Exceeded' error on most online judges due to the O(n^2) complexity.
A more efficient approach is to iterate through the price list just once. We maintain two variables: the minimum price encountered so far and the maximum profit seen. This allows us to find the solution in linear time.
Algorithm
- Initialize
minPricetoInteger.MAX_VALUE. - Initialize
maxProfitto 0. - Iterate through the
pricesarray with an indexifrom 0 ton-1. - For each price
prices[i]:- If
prices[i]is less thanminPrice, updateminPrice = prices[i]. - Else, calculate the potential profit
prices[i] - minPrice. If this is greater thanmaxProfit, updatemaxProfit.
- If
- After the loop, return
maxProfit.
Walkthrough
This optimized approach avoids the nested loops by iterating through the prices array a single time. The key idea is that the maximum profit at any given day i is the difference between the price on that day prices[i] and the minimum price encountered on any day before i.
We initialize minPrice to a very large number (or the first price) and maxProfit to 0.
We then traverse the prices array. For each price, we first check if it's a new minimum price. If it is, we update minPrice. Then, we calculate the potential profit if we were to sell on the current day using the minPrice found so far (prices[i] - minPrice). We update maxProfit if this potential profit is larger than the current maxProfit.
By the end of the single pass, we will have found the overall maximum profit.
class Solution { public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; } else if (prices[i] - minPrice > maxProfit) { maxProfit = prices[i] - minPrice; } } return maxProfit; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Extremely efficient with linear time complexity.
Uses constant extra space.
This is the optimal solution for this problem.
Cons
May be slightly less intuitive to devise compared to the brute-force method.
Solutions
Solution
public class Solution { public int MaxProfit(int[] prices) { int ans = 0, mi = prices[0]; foreach(int v in prices) { ans = Math.Max(ans, v - mi); mi = Math.Min(mi, v); } return ans; }}class Solution {public int maxProfit(int[] prices) { int ans = 0, mi = prices[0]; for (int v : prices) { ans = Math.max(ans, v - mi); mi = Math.min(mi, v); } return ans; }}/** * @param {number[]} prices * @return {number} */ var maxProfit = function ( prices,) { let ans = 0; let mi = prices[0]; for (const v of prices) { ans = Math.max(ans, v - mi); mi = Math.min(mi, v); } return ans;};class Solution {public: int maxProfit(vector<int> &prices) { int ans = 0, mi = prices[0]; for (int &v : prices) { ans = max(ans, v - mi); mi = min(mi, v); } return ans; }};''' >>> import math >>> a = math.inf >>> a inf >>> x = float('-inf') >>> y = float('inf') >>> print(x < y) # Output: True True >>> >>> z = -math.inf >>> x==z True ''' class Solution : def maxProfit ( self , prices : List [ int ]) -> int : ans , mi = 0 , inf for v in prices : mi = min ( mi , v ) ans = max ( ans , v - mi ) return ans ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ if not prices : return 0 ans = 0 pre = prices [ 0 ] for i in range ( 1 , len ( prices )): pre = min ( pre , prices [ i ]) ans = max ( prices [ i ] - pre , ans ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.