Best Time to Buy and Sell Stock
Problem link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Problem Statement
You are given an array prices where prices[i] is the price of a given stock on the i-th 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. If you cannot achieve any profit, return 0.
Input
An integer array prices.
Output
An integer representing the maximum profit.
Example
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.
Explanation
We look for the lowest price seen so far and calculate the potential profit if we sold at the current price. The maximum of these profits is our answer.
Brute Force
Intuition
Try every possible pair of (buy day, sell day) where the sell day is after the buy day, and keep track of the maximum difference.
Approach
- Use nested loops: i from 0 to n-2, j from i+1 to n-1.
- Calculate profit = prices[j] - prices[i].
- Update maxi = max(maxi, profit).
Dry Run
prices = [7, 1, 5]
- (7,1): profit -6
- (7,5): profit -2
- (1,5): profit 4 Max profit: 4
Code (Java)
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit;
}
}
Complexity Analysis
We check all possible pairs of days.
Optimal Solution
Intuition
As we traverse the array, we only care about two things: the minimum price we've seen so far and the maximum profit we can make by selling at the current price.
Approach
- Initialize
minPriceto infinity andmaxProfitto 0. - Iterate through each price in the array.
- Update
minPriceif the current price is lower. - Otherwise, calculate
currentProfit = currentPrice - minPrice. - Update
maxProfitifcurrentProfitis greater.
Dry Run
prices = [7,1,5,3,6,4]
- price=7: min=7, maxP=0
- price=1: min=1, maxP=0
- price=5: min=1, maxP=4 (5-1)
- price=3: min=1, maxP=4
- price=6: min=1, maxP=5 (6-1)
- price=4: min=1, maxP=5
Code (Java)
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
}
Complexity Analysis
We traverse the price array exactly once.
Quick Revision (Brute Force)
- Check all pairs (i, j) where j > i
- O(N^2) time
Quick Revision (Optimal)
- Greedy approach
- Maintain minPrice so far
- Maximize (currentPrice - minPrice)
- O(N) time, O(1) space