Best Time to Buy and Sell Stock
Problem Description
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:
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:
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
Using a brute force approach, we can try all possible combinations of buying and selling days and compute the profit for each combination. The maximum of these profits will be our answer.
Steps:
- Iterate through the list of prices with two nested loops.
- The outer loop will represent the buying day.
- The inner loop will represent the selling day.
- For each combination of buying and selling days, calculate the profit.
- Maintain a variable to keep track of the maximum profit observed.
Code:
- Time Complexity: O(n^2) due to the two nested loops.
- Space Complexity: O(1) as no extra space is used.
2. One Pass Approach
Intuition:
Instead of trying all possible pairs of buy and sell days, we can iterate through the list of prices once while keeping track of the minimum price encountered so far. At each step, we calculate what the profit would be if we sold at the current price, and update the maximum profit correspondingly.
Approach:
Scan prices left to right while maintaining:
- minPrice: the lowest price seen so far (best day to have bought before or on today).
- maxProfit: the best profit achievable if we must sell on or after that minPrice day and on or before today.
At each day’s price p:
- Update
minPrice = min(minPrice, p). This locks in the cheapest buy seen so far. - Compute potential profit if we sell today:
p - minPrice. - Update
maxProfit = max(maxProfit, p - minPrice).
Return maxProfit after the scan.
Why this works?
- Any valid trade is an ordered pair
(buyDay < sellDay). When you stand onsellDay = i, the best buy day is simply the cheapest price among days0..i. That’s exactlyminPriceafter scanning up toi. - So the optimal profit that ends at day
iisprices[i] - minPrice. By checking this at everyi, we consider the best “sell-today” profit for every possible sell day. - The global optimum is the maximum over all these per-day profits, which we maintain as
maxProfit.
Code:
- Time Complexity: O(n) due to single loop.
- Space Complexity: O(1) as no extra space is used.