Best Time to Buy and Sell Stock solution and explanation
Mastercard
9 more videos on this problem
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - PythonNeetCode · 8:46 · 1.1M views
Best Time To Buy & Sell Stock 1 (LeetCode 121) | Full solution with visuals and animationNikhil Lohia · 14:43 · 83K views
LeetCode Best Time to Buy and Sell Stock Solution Explained - JavaNick White · 3:46 · 58K views
Best Time to Buy and Sell Stock - Leetcode 121 - Arrays & Strings (Python)Greg Hogg · 5:49 · 47K views
LeetCode 121: Best Time to Buy and Sell StockAbstracted Away · 8:13 · 39K views
Best Time to Buy and Sell Stock | Leetcode 121 | Top 150 interview question seriesTechnosage · 9:11 · 18K views
LeetCode Solution - 121 Best time to Buy and Sell Stock | JavascriptThinkFWD · 12:24 · 12K views
Best Time To Buy And Sell Stock - LeetCode 121 - JavaScriptAlgoJS · 5:23 · 7K views
Best Time to Buy and Sell Stock - Leetcode 121 - Python | Malayalam Coding SolutionWeCode Community · 12:35 · 4K views
How To Think About "Best Time to Buy And Sell Stock" (LeetCode 121)Gordon Zhu · 8:36 · 1K views
The problem
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
Approach overview
Problem Overview: You are given an array where prices[i] is the stock price on day i. You must choose one day to buy and a later day to sell to maximize profit. If no profitable transaction exists, return 0.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward solution checks every possible pair of days. For each day i, treat it as the buying day and compare it with every later day j as the selling day. Compute the profit prices[j] - prices[i] and track the maximum value. This approach uses nested loops over the array, so the time complexity grows quadratically. It works for small inputs and helps verify the logic of the problem, but becomes slow for large datasets.
Approach 2: Single Pass with Tracking Minimum Price (O(n) time, O(1) space)
The optimal solution scans the array once while maintaining the lowest price seen so far. At each step, treat the current price as a potential selling price and compute the profit using currentPrice - minPrice. If this profit exceeds the best profit recorded so far, update the result. Otherwise, update minPrice when a lower price appears. This works because the best transaction must buy at the lowest price before the sell day.
This technique resembles a simplified dynamic programming or greedy strategy: maintain state (minPrice) while iterating through the array and update the best answer incrementally. Only two variables are required, so space usage stays constant. The algorithm performs exactly one pass over the data, making it efficient even for very large inputs.
Recommended for interviews: Interviewers expect the single-pass minimum tracking approach. The brute force solution demonstrates baseline reasoning and correctness, but the O(n) scan shows you recognize the key insight: the best sell decision depends only on the smallest price seen before that day. Implementing this efficiently with constant space is the standard interview solution.
Approach 1: Approach 1: Single Pass with Tracking Minimum Price
In this approach, we traverse the prices array while keeping track of the minimum price seen so far and calculate the maximum profit we could achieve if we sold on that day. The maximum profit is updated accordingly through each iteration.
This approach makes a single pass through the array (O(n) time complexity) and uses constant space (O(1) space complexity).
def maxProfit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit
prices = [7, 1, 5, 3, 6, 4]
print("Max Profit:", maxProfit(prices))class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
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;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println("Max Profit: " + sol.maxProfit(prices));
}
}#include <iostream>
#include <vector>
int maxProfit(std::vector<int>& prices) {
if (prices.empty()) return 0;
int min_price = prices[0];
int max_profit = 0;
for (int i = 1; i < prices.size(); i++) {
min_price = std::min(min_price, prices[i]);
max_profit = std::max(max_profit, prices[i] - min_price);
}
return max_profit;
}
int main() {
std::vector<int> prices = {7, 1, 5, 3, 6, 4};
std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
return 0;
}function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (let price of prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
const prices = [7, 1, 5, 3, 6, 4];
console.log("Max Profit:", maxProfit(prices));#include <stdio.h>
int maxProfit(int* prices, int pricesSize) {
if (pricesSize == 0) return 0;
int min_price = prices[0];
int max_profit = 0;
for (int i = 1; i < pricesSize; i++) {
if (prices[i] < min_price) {
min_price = prices[i];
} else if (prices[i] - min_price > max_profit) {
max_profit = prices[i] - min_price;
}
}
return max_profit;
}
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int size = sizeof(prices)/sizeof(prices[0]);
printf("Max Profit: %d\n", maxProfit(prices, size));
return 0;
}using System;
public class Solution {
public int MaxProfit(int[] prices) {
if (prices.Length == 0) return 0;
int minPrice = int.MaxValue;
int maxProfit = 0;
foreach (int price in prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] prices = {7, 1, 5, 3, 6, 4};
Console.WriteLine("Max Profit: " + sol.MaxProfit(prices));
}
}This Python solution utilizes a float('inf') as an initial minimum price to ensure any price will be lower, updating min_price and max_profit accordingly during each iteration over prices.
Time Complexity: O(n), where n is the number of days.
Space Complexity: O(1).
Approach 2: Approach 2: Brute Force (For Educational Purposes)
This approach considers all possible pairs of buy and sell days, calculating the profit for each combination. It is straightforward but inefficient due to its O(n^2) time complexity, which is impractical for large inputs.
def maxProfit(prices):
max_profit = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
profit = prices[j] - prices[i]
if profit > max_profit:
max_profit = profit
return max_profit
prices = [7, 1, 5, 3, 6, 4]
print("Max Profit (Brute Force):", maxProfit(prices))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 > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println("Max Profit (Brute Force): " + sol.maxProfit(prices));
}
}#include <iostream>
#include <vector>
int maxProfit(std::vector<int>& prices) {
int max_profit = 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 > max_profit) {
max_profit = profit;
}
}
}
return max_profit;
}
int main() {
std::vector<int> prices = {7, 1, 5, 3, 6, 4};
std::cout << "Max Profit (Brute Force): " << maxProfit(prices) << std::endl;
return 0;
}function maxProfit(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 > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
const prices = [7, 1, 5, 3, 6, 4];
console.log("Max Profit (Brute Force):", maxProfit(prices));#include <stdio.h>
int maxProfit(int* prices, int pricesSize) {
int max_profit = 0;
for (int i = 0; i < pricesSize; i++) {
for (int j = i+1; j < pricesSize; j++) {
int profit = prices[j] - prices[i];
if (profit > max_profit) {
max_profit = profit;
}
}
}
return max_profit;
}
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int size = sizeof(prices)/sizeof(prices[0]);
printf("Max Profit (Brute Force): %d\n", maxProfit(prices, size));
return 0;
}using System;
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 > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] prices = {7, 1, 5, 3, 6, 4};
Console.WriteLine("Max Profit (Brute Force): " + sol.MaxProfit(prices));
}
}This Python brute force approach manually examines each potential sell price following every buy price, updating max_profit with the highest difference captured.
Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).
Approach 3: Enumerate + Maintain the Minimum Value of the Prefix
We can enumerate each element of the array nums as the selling price. Then we need to find a minimum value in front of it as the purchase price to maximize the profit.
Therefore, we use a variable mi to maintain the prefix minimum value of the array nums. Then we traverse the array nums and for each element v, calculate the difference between it and the minimum value mi in front of it, and update the answer to the maximum of the difference. Then update mi = min(mi, v). Continue to traverse the array nums until the traversal ends.
Finally, return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function maxProfit(prices: number[]): number {
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;
}func maxProfit(prices []int) (ans int) {
mi := prices[0]
for _, v := range prices {
ans = max(ans, v-mi)
mi = min(mi, v)
}
return
}impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut ans = 0;
let mut mi = prices[0];
for &v in &prices {
ans = ans.max(v - mi);
mi = mi.min(v);
}
ans
}
}class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$ans = 0;
$mi = $prices[0];
foreach ($prices as $v) {
$ans = max($ans, $v - $mi);
$mi = min($mi, $v);
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Single Pass with Tracking Minimum Price | Time Complexity: O(n), where n is the number of days. |
| Approach 2: Brute Force (For Educational Purposes) | Time Complexity: O(n^2), where n is the number of days. |
| Enumerate + Maintain the Minimum Value of the Prefix | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Check All Buy/Sell Pairs) | O(n²) | O(1) | Educational baseline to understand profit calculation and validate logic |
| Single Pass with Minimum Price Tracking | O(n) | O(1) | Optimal solution for interviews and production; handles large arrays efficiently |
Frequently asked questions
Is Best Time to Buy and Sell Stock easy or hard?
Best Time to Buy and Sell Stock is categorized as an Easy problem on LeetCode with an acceptance rate around the mid‑50% range. The challenge lies in recognizing that you only need to track the minimum price so far instead of checking all possible buy and sell pairs.
Best Time to Buy and Sell Stock Python/Java solution
In Python or Java, iterate through the prices array while tracking minPrice and maxProfit. Update minPrice when a smaller value appears and compute profit using currentPrice minus minPrice. This implementation runs in O(n) time and O(1) space and is typically under 10 lines of code.
How to solve Best Time to Buy and Sell Stock in O(n)?
Iterate through the price array while tracking the smallest price encountered so far. At each step calculate potential profit as prices[i] minus minPrice and update the maximum profit. If the current price is lower than minPrice, update it. This single pass guarantees O(n) time and constant space.
What is the best approach for Best Time to Buy and Sell Stock?
The best approach is a single-pass scan that tracks the minimum stock price seen so far. For each price, compute the profit if you sold that day using currentPrice minus minPrice. Update the maximum profit and minimum price while iterating. This runs in O(n) time and O(1) space.
Is Best Time to Buy and Sell Stock asked at Google/Amazon/Meta?
Best Time to Buy and Sell Stock is a common interview question across large tech companies including Amazon, Google, Meta, and Microsoft. It tests understanding of array traversal, greedy thinking, and recognizing optimization opportunities from a brute force approach.
What data structure is used in Best Time to Buy and Sell Stock?
The problem primarily uses a simple array traversal. The optimal algorithm maintains two variables—minimum price so far and maximum profit—while iterating through the array, so no additional data structures like hash maps or stacks are required.
What is the time complexity of Best Time to Buy and Sell Stock?
The optimal solution runs in O(n) time because the array is scanned once while maintaining the minimum price and maximum profit. Space complexity is O(1) since only a few variables are stored regardless of input size.