121. Best Time to Buy and Sell Stock - Leetcode Solution
Solution codeđź’ˇ Step-by-Step Thought Process
Brute Force
- Understand the Problem:
- We are tasked with finding the highest possible profit from buying a stock on one day and selling it on a later day.
- The profit is calculated as
prices[j] - prices[i]whereiis the buy day andjis the sell day (withj > i).
- Check All Pairs of Days:
- We iterate over each possible day
ias the buying day. - For each buying day
i, we iterate over all subsequent daysj(wherej > i) as the selling day.
- We iterate over each possible day
- Calculate Profit for Each Pair:
- For each pair of buy and sell days, calculate the profit as
prices[j] - prices[i]. - If the profit is positive (i.e., the stock price on day
jis higher than on dayi), we check if this profit is the highest profit seen so far.
- For each pair of buy and sell days, calculate the profit as
- Return the Maximum Profit:
- Once all pairs are checked, the highest value for
max_profitwill be the answer.
- Once all pairs are checked, the highest value for
Code Solution (Brute Force)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
for i in range(len(prices)):
for j in range(i+1, len(prices)):
profit = prices[j] - prices[i]
if profit > 0:
max_profit = max(max_profit, profit)
return max_profit
# Time: O(N^2) (Brute Force)
# Space: O(1)
# This was modified from the video explanation to let max_profit = 0, this is better#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
int profit = prices[j] - prices[i];
if (profit > 0) {
maxProfit = max(maxProfit, profit);
}
}
}
return maxProfit;
}
};public 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++) {
int profit = prices[j] - prices[i];
if (profit > 0) {
maxProfit = Math.max(maxProfit, profit);
}
}
}
return maxProfit;
}
}/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
let profit = prices[j] - prices[i];
if (profit > 0) {
maxProfit = Math.max(maxProfit, profit);
}
}
}
return maxProfit;
};Why the Brute-Force Solution is Inefficient
The brute-force solution checks every possible pair of buy and sell days using nested loops, leading to:
- Time Complexity: O(n²), where n is the length of the prices array, as each day is compared with every subsequent day.
- Space Complexity: O(1), as only a constant amount of extra space is used.
- Performance Issue: For large arrays, the quadratic time complexity results in significant slowdowns, making it impractical for large inputs.
Optimal Solution
The optimal solution uses a single pass to track the minimum price seen so far, achieving O(n) time complexity:
- Track the Minimum Price:
- Instead of checking all pairs of days, we can track the lowest price encountered so far as we iterate through the list.
- This allows us to calculate the potential profit at each step by subtracting the current minimum price from the current price.
- Update Maximum Profit Efficiently:
- As we go through each price, we only calculate the profit for the current day using the minimum price up to that point.
- If the calculated profit is greater than the previous maximum profit, we update the maximum profit.
- Single Pass Through the Prices:
- By iterating through the list once, we avoid the nested loops of the brute force solution, reducing the time complexity.
Code Solution (Optimal)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Time: O(n)
# Space: O(1)
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
profit = price - min_price
if profit > max_profit:
max_profit = profit
return max_profit
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
}
int profit = price - minPrice;
if (profit > maxProfit) {
maxProfit = profit;
}
}
return maxProfit;
}
};
public class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
}
int profit = price - minPrice;
if (profit > maxProfit) {
maxProfit = profit;
}
}
return maxProfit;
}
}
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (const price of prices) {
if (price < minPrice) {
minPrice = price;
}
const profit = price - minPrice;
if (profit > maxProfit) {
maxProfit = profit;
}
}
return maxProfit;
};
Detailed Explanation
Understanding the Problem: Best Time to Buy and Sell Stock
The “Best Time to Buy and Sell Stock” problem is one of the most fundamental algorithm questions involving arrays and financial profit optimization.
Given an array of stock prices where prices[i] represents the stock price on the ith day, your goal is to determine the maximum profit you can achieve by making one buy and one sell.
You must buy before you sell.
Why It’s Important
This problem teaches a key concept in algorithm design: finding optimal values while scanning a sequence only once. It demonstrates how to convert a seemingly quadratic-time problem into an efficient linear-time solution using a greedy approach and running minimum tracking.
Naive Approach (Brute-Force)
A straightforward solution is to consider every possible pair of days (i, j) such that i < j. For each pair, you compute the profit prices[j] - prices[i], and track the maximum profit.
This approach works correctly but is inefficient for large inputs due to its nested loop structure.
Time Complexity: O(n²)
Space Complexity: O(1)
Optimal Linear-Time Solution (Greedy)
Instead of checking every pair, we can achieve an optimal solution in O(n) time using a single pass. The main idea is to:
- Track the lowest price seen so far (which is the best day to buy).
- At each day, calculate the potential profit if we sold at the current price.
- Update the maximum profit if this potential profit is higher.
This greedy strategy ensures that we always buy at the lowest price and sell later at the highest price that gives the best return.
Step-by-Step Example
Suppose we have the array prices = [7, 1, 5, 3, 6, 4]. Let’s walk through it:
- Day 0: Price is 7.
min_price = 7, no profit yet. - Day 1: Price is 1. New minimum →
min_price = 1 - Day 2: Price is 5. Profit = 5 - 1 = 4 →
max_profit = 4 - Day 3: Price is 3. Profit = 3 - 1 = 2 → no update
- Day 4: Price is 6. Profit = 6 - 1 = 5 →
max_profit = 5 - Day 5: Price is 4. Profit = 4 - 1 = 3 → no update
The final answer is 5, which is the maximum profit possible from buying on day 1 (price 1) and selling on day 4 (price 6).
Edge Cases to Consider
- If the prices array is empty or contains only one price, return 0 — you can’t sell without buying first.
- If prices are in descending order (e.g.,
[7,6,4,3,1]), no profit is possible → return 0. - The function should never return negative profit — it’s better to make no transaction than to lose money.
Time and Space Complexity
Time Complexity: O(n), where n is the length of the prices array. We make only a single pass through the array.
Space Complexity: O(1), since we use only two variables: min_price and max_profit.
Conclusion
The “Best Time to Buy and Sell Stock” problem is a classic example of optimizing over a sequence using minimal memory and maximum efficiency. It introduces critical techniques like maintaining a running minimum and calculating deltas on the fly — useful skills in both interviews and real-world algorithmic problems.