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 ith day.

You want to maximize your profit by choosing a single day to buy one stock and 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.

What to notice first

• You can only make one transaction — buy once, sell once.
• You must buy before you sell — the sell day must come after the buy day.
• The goal is to find the pair of days with the maximum gap (sell price - buy price).
• You don’t have to trade at all — if prices only fall, you can return 0.

Examples

Input	Output	Explanation
[7, 1, 5, 3, 6, 4]	5	Buy at day 1 (price = 1), sell at day 4 (price = 6), profit = 6 - 1 = 5
[7, 6, 4, 3, 1]	0	Prices are falling. No profit is possible.
[2, 4, 1, 7, 5, 11]	9	Buy at day 0 (price = 2), sell at day 5 (price = 11), profit = 11 - 2 = 9

Constraints

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Real-World Applications

Where this pattern appears

• Trading systems — finding the best entry and exit points for a single stock position.
• Portfolio optimization — identifying profitable time windows for buying and selling assets.
• Price monitoring — flagging periods when an asset hits a local minimum and maximum in sequence.
• Historical analysis — determining the best buy-sell window in any historical price series.

Complexity Comparison

Approach	Time	Space	Best When
Single Pass	O(n)	O(1)	General case — fast, memory-efficient, tracks min price
Brute Force	O(n²)	O(1)	Learning the pattern, arrays are very small

Which approach should you learn first?

• Pick Single Pass for the optimal solution — it is straightforward and O(n).
• Pick Brute Force if you are just starting to understand the problem or need to explain the idea simply.

Best For Speed

Single Pass

O(n) time · O(1) space

Simple to Learn

Brute Force

O(n²) time · O(1) space

Approach 1: Single Pass with Min Price Tracking

★ Recommended

Keep track of the lowest price seen so far as you iterate through the prices. At each day, calculate the profit if you sell at that day’s price. Update the maximum profit whenever a better profit is found.

The key insight is that the best selling day for any given price is always after the minimum price we have seen. By scanning left to right, we ensure the buy day always comes before the sell day.

⏱ Time O(n) Single pass, no extra structures 💾 Space O(1) Only two variables

Step-by-step Example

Input: prices = [7, 1, 5, 3, 6, 4]

Day	Price	Min Price Seen	Profit if Sell Today	Max Profit
0	7	7	—	0
1	1	1	1 - 1 = 0	0
2	5	1	5 - 1 = 4	4
3	3	1	3 - 1 = 2	4
4	6	1	6 - 1 = 5	5 ✓
5	4	1	4 - 1 = 3	5

Animated walkthrough

How single pass finds the maximum profit

Use Next or Autoplay to watch the minimum price and maximum profit update as you scan through the prices.

Back Autoplay Next Reset

Step 1 of 6

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function maxProfitSinglePass(prices):
    if prices.length < 2:
        return 0

    minPrice = prices[0]
    maxProfit = 0

    for i from 1 to len(prices) - 1:
        profit = prices[i] - minPrice
        maxProfit = max(maxProfit, profit)
        minPrice = min(minPrice, prices[i])

    return maxProfit

Solution Code

Python

best_time_to_buy_and_sell_stock_single_pass.py

# Approach: Single Pass with Min Price Tracking
# Track the minimum price seen so far and calculate the maximum profit at each price.
# When we see a new price, we check the profit if we sell at that price.
#
# Time Complexity: O(n) — single pass
# Space Complexity: O(1)

from typing import List


def max_profit(prices: List[int]) -> int:
    if not prices or len(prices) < 2:
        return 0

    min_price = prices[0]
    max_profit_val = 0

    for price in prices[1:]:
        profit = price - min_price
        max_profit_val = max(max_profit_val, profit)
        min_price = min(min_price, price)

    return max_profit_val


print(max_profit([7, 1, 5, 3, 6, 4]))  # 5
print(max_profit([7, 6, 4, 3, 1]))     # 0
print(max_profit([2, 4, 1, 7, 5, 11])) # 9

C++

best_time_to_buy_and_sell_stock_single_pass.cpp

// Approach: Single Pass with Min Price Tracking
// Track the minimum price seen so far and calculate the maximum profit at each price.
// When we see a new price, we check the profit if we sell at that price.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int maxProfit(vector<int>& prices) {
    if (prices.empty() || prices.size() < 2) {
        return 0;
    }

    int minPrice = prices[0];
    int maxProfitVal = 0;

    for (int i = 1; i < prices.size(); i++) {
        int profit = prices[i] - minPrice;
        maxProfitVal = max(maxProfitVal, profit);
        minPrice = min(minPrice, prices[i]);
    }

    return maxProfitVal;
}


int main() {
    vector<int> prices1 = {7, 1, 5, 3, 6, 4};
    cout << maxProfit(prices1) << endl;  // 5

    vector<int> prices2 = {7, 6, 4, 3, 1};
    cout << maxProfit(prices2) << endl;  // 0

    vector<int> prices3 = {2, 4, 1, 7, 5, 11};
    cout << maxProfit(prices3) << endl;  // 9

    return 0;
}

Java

best_time_to_buy_and_sell_stock_single_pass.java

// Approach: Single Pass with Min Price Tracking
// Track the minimum price seen so far and calculate the maximum profit at each price.
// When we see a new price, we check the profit if we sell at that price.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minPrice = prices[0];
        int maxProfitVal = 0;

        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - minPrice;
            maxProfitVal = Math.max(maxProfitVal, profit);
            minPrice = Math.min(minPrice, prices[i]);
        }

        return maxProfitVal;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        int[] prices1 = {7, 1, 5, 3, 6, 4};
        System.out.println(sol.maxProfit(prices1));  // 5

        int[] prices2 = {7, 6, 4, 3, 1};
        System.out.println(sol.maxProfit(prices2));  // 0

        int[] prices3 = {2, 4, 1, 7, 5, 11};
        System.out.println(sol.maxProfit(prices3));  // 9
    }
}

JavaScript

best_time_to_buy_and_sell_stock_single_pass.js

// Approach: Single Pass with Min Price Tracking
// Track the minimum price seen so far and calculate the maximum profit at each price.
// When we see a new price, we check the profit if we sell at that price.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1)

function maxProfit(prices) {
    if (!prices || prices.length < 2) {
        return 0;
    }

    let minPrice = prices[0];
    let maxProfitVal = 0;

    for (let i = 1; i < prices.length; i++) {
        const price = prices[i];
        const profit = price - minPrice;
        maxProfitVal = Math.max(maxProfitVal, profit);
        minPrice = Math.min(minPrice, price);
    }

    return maxProfitVal;
}


console.log(maxProfit([7, 1, 5, 3, 6, 4]));  // 5
console.log(maxProfit([7, 6, 4, 3, 1]));     // 0
console.log(maxProfit([2, 4, 1, 7, 5, 11])); // 9

Rust

best_time_to_buy_and_sell_stock_single_pass.rs

// Approach: Single Pass with Min Price Tracking
// Track the minimum price seen so far and calculate the maximum profit at each price.
// When we see a new price, we check the profit if we sell at that price.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1)

pub fn max_profit(prices: Vec<i32>) -> i32 {
    if prices.is_empty() || prices.len() < 2 {
        return 0;
    }

    let mut min_price = prices[0];
    let mut max_profit_val = 0;

    for i in 1..prices.len() {
        let profit = prices[i] - min_price;
        max_profit_val = max_profit_val.max(profit);
        min_price = min_price.min(prices[i]);
    }

    max_profit_val
}

fn main() {
    println!("{}", max_profit(vec![7, 1, 5, 3, 6, 4]));  // 5
    println!("{}", max_profit(vec![7, 6, 4, 3, 1]));     // 0
    println!("{}", max_profit(vec![2, 4, 1, 7, 5, 11])); // 9
}

Go

best_time_to_buy_and_sell_stock_single_pass.go

// Approach: Single Pass with Min Price Tracking
// Track the minimum price seen so far and calculate the maximum profit at each price.
// When we see a new price, we check the profit if we sell at that price.
//
// Time Complexity: O(n) — single pass
// Space Complexity: O(1)

package main

func maxProfit(prices []int) int {
  if len(prices) < 2 {
    return 0
  }

  minPrice := prices[0]
  maxProfitVal := 0

  for i := 1; i < len(prices); i++ {
    profit := prices[i] - minPrice
    if profit > maxProfitVal {
      maxProfitVal = profit
    }
    if prices[i] < minPrice {
      minPrice = prices[i]
    }
  }

  return maxProfitVal
}

// Test cases:
// maxProfit([]int{7, 1, 5, 3, 6, 4})  // 5
// maxProfit([]int{7, 6, 4, 3, 1})     // 0
// maxProfit([]int{2, 4, 1, 7, 5, 11}) // 9

Approach 2: Brute Force

✓ Simple

For each pair of days (i, j) where i < j, calculate the profit as prices[j] - prices[i] and track the maximum. This is the most direct method but becomes slow for large arrays.

⏱ Time O(n²) All pairs checked 💾 Space O(1) No extra memory

Step-by-step Example

Input: prices = [7, 1, 5, 3, 6, 4]

Buy Day	Sell Day	Buy Price	Sell Price	Profit
0	1	7	1	-6
0	2	7	5	-2
0	3	7	3	-4
0	4	7	6	-1
0	5	7	4	-3
1	2	1	5	4
1	3	1	3	2
1	4	1	6	5 ✓
1	5	1	4	3
…	…	…	…	…

Pseudocode

function maxProfitBruteForce(prices):
    n = len(prices)
    maxProfit = 0

    for i from 0 to n - 1:
        for j from i + 1 to n - 1:
            profit = prices[j] - prices[i]
            maxProfit = max(maxProfit, profit)

    return maxProfit

Solution Code

Python

best_time_to_buy_and_sell_stock_brute_force.py

# Approach: Brute Force
# Try every pair (i, j) where i < j. Profit = prices[j] - prices[i].
# Track the maximum profit across all pairs.
#
# Time Complexity: O(n²) — nested loops over all pairs
# Space Complexity: O(1)

from typing import List


def max_profit(prices: List[int]) -> int:
    n = len(prices)
    max_profit_val = 0

    for i in range(n):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            max_profit_val = max(max_profit_val, profit)

    return max_profit_val


print(max_profit([7, 1, 5, 3, 6, 4]))  # 5
print(max_profit([7, 6, 4, 3, 1]))     # 0
print(max_profit([2, 4, 1, 7, 5, 11])) # 9

C++

best_time_to_buy_and_sell_stock_brute_force.cpp

// Approach: Brute Force
// Try every pair (i, j) where i < j. Profit = prices[j] - prices[i].
// Track the maximum profit across all pairs.
//
// Time Complexity: O(n²) — nested loops over all pairs
// Space Complexity: O(1)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int maxProfitVal = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int profit = prices[j] - prices[i];
            maxProfitVal = max(maxProfitVal, profit);
        }
    }

    return maxProfitVal;
}


int main() {
    vector<int> prices1 = {7, 1, 5, 3, 6, 4};
    cout << maxProfit(prices1) << endl;  // 5

    vector<int> prices2 = {7, 6, 4, 3, 1};
    cout << maxProfit(prices2) << endl;  // 0

    vector<int> prices3 = {2, 4, 1, 7, 5, 11};
    cout << maxProfit(prices3) << endl;  // 9

    return 0;
}

Java

best_time_to_buy_and_sell_stock_brute_force.java

// Approach: Brute Force
// Try every pair (i, j) where i < j. Profit = prices[j] - prices[i].
// Track the maximum profit across all pairs.
//
// Time Complexity: O(n²) — nested loops over all pairs
// Space Complexity: O(1)

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int maxProfitVal = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int profit = prices[j] - prices[i];
                maxProfitVal = Math.max(maxProfitVal, profit);
            }
        }

        return maxProfitVal;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        int[] prices1 = {7, 1, 5, 3, 6, 4};
        System.out.println(sol.maxProfit(prices1));  // 5

        int[] prices2 = {7, 6, 4, 3, 1};
        System.out.println(sol.maxProfit(prices2));  // 0

        int[] prices3 = {2, 4, 1, 7, 5, 11};
        System.out.println(sol.maxProfit(prices3));  // 9
    }
}

JavaScript

best_time_to_buy_and_sell_stock_brute_force.js

// Approach: Brute Force
// Try every pair (i, j) where i < j. Profit = prices[j] - prices[i].
// Track the maximum profit across all pairs.
//
// Time Complexity: O(n²) — nested loops over all pairs
// Space Complexity: O(1)

function maxProfit(prices) {
    const n = prices.length;
    let maxProfitVal = 0;

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const profit = prices[j] - prices[i];
            maxProfitVal = Math.max(maxProfitVal, profit);
        }
    }

    return maxProfitVal;
}


console.log(maxProfit([7, 1, 5, 3, 6, 4]));  // 5
console.log(maxProfit([7, 6, 4, 3, 1]));     // 0
console.log(maxProfit([2, 4, 1, 7, 5, 11])); // 9

Rust

best_time_to_buy_and_sell_stock_brute_force.rs

// Approach: Brute Force
// Try every pair (i, j) where i < j. Profit = prices[j] - prices[i].
// Track the maximum profit across all pairs.
//
// Time Complexity: O(n²) — nested loops over all pairs
// Space Complexity: O(1)

pub fn max_profit(prices: Vec<i32>) -> i32 {
    let n = prices.len();
    let mut max_profit_val = 0;

    for i in 0..n {
        for j in (i + 1)..n {
            let profit = prices[j] - prices[i];
            max_profit_val = max_profit_val.max(profit);
        }
    }

    max_profit_val
}

fn main() {
    println!("{}", max_profit(vec![7, 1, 5, 3, 6, 4]));  // 5
    println!("{}", max_profit(vec![7, 6, 4, 3, 1]));     // 0
    println!("{}", max_profit(vec![2, 4, 1, 7, 5, 11])); // 9
}

Go

best_time_to_buy_and_sell_stock_brute_force.go

// Approach: Brute Force
// Try every pair (i, j) where i < j. Profit = prices[j] - prices[i].
// Track the maximum profit across all pairs.
//
// Time Complexity: O(n²) — nested loops over all pairs
// Space Complexity: O(1)

package main

func maxProfitBruteForce(prices []int) int {
  n := len(prices)
  maxProfitVal := 0

  for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ {
      profit := prices[j] - prices[i]
      if profit > maxProfitVal {
        maxProfitVal = profit
      }
    }
  }

  return maxProfitVal
}

// Test cases:
// maxProfitBruteForce([]int{7, 1, 5, 3, 6, 4})  // 5
// maxProfitBruteForce([]int{7, 6, 4, 3, 1})     // 0
// maxProfitBruteForce([]int{2, 4, 1, 7, 5, 11}) // 9

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

best_time_to_buy_and_sell_stock_space_optimized.py

"""
Solution for Best Time to Buy and Sell Stock
"""

def solve():
    """Implementation for approach 3 of Best Time to Buy and Sell Stock"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

best_time_to_buy_and_sell_stock_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Best Time to Buy and Sell Stock
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

BestTimeToBuyAndSellStockSpaceOptimized.java

/**
 * Solution for Best Time to Buy and Sell Stock
 * Approach 3
 */
public class BestTimeToBuyAndSellStockSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

best_time_to_buy_and_sell_stock_space_optimized.js

/**
 * Solution for Best Time to Buy and Sell Stock
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

best_time_to_buy_and_sell_stock_space_optimized.rs

/// Solution for Best Time to Buy and Sell Stock
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

best_time_to_buy_and_sell_stock_space_optimized.go

package main

import "fmt"

// Solution for Best Time to Buy and Sell Stock
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Selling before buying — forgetting to check that j > i, or using past prices as sell prices. Always ensure the sell day comes after the buy day.
• Off-by-one errors — starting the second loop at i instead of i + 1, which allows buying and selling on the same day.
• Initializing maxProfit to a price value — initialize to 0, not prices[0], since zero profit is always achievable (don’t trade).
• Not handling small arrays — edge case: arrays with only one element have no valid transaction, so return 0.
• Updating minPrice after checking profit — in the single pass approach, always update minPrice after calculating profit for the current day.

Related Problems

• Best Time to Buy and Sell Stock II ↗ Medium #122
• Best Time to Buy and Sell Stock III ↗ Hard #123
• Best Time to Buy and Sell Stock IV ↗ Hard #188
• Best Time to Buy and Sell Stock with Cooldown ↗ Medium #309

Interview Tips

Key trade-offs to discuss

• Single Pass vs Brute Force: O(n) vs O(n²) is a massive difference. In interviews, lead with the single pass approach.
• Why track minimum price? Instead of comparing every pair, we keep the best buying opportunity we have seen so far. This is a greedy insight.
• Follow-up — multiple transactions: Problem #122 allows unlimited buy-sell pairs. The techniques differ, but the single-pass mindset carries over.
• Edge cases to mention:
  • Single-element array (no transaction possible, return 0)
  • Falling prices (all differences are negative, so max is 0)
  • Rising prices (best profit is last - first)
  • Duplicate prices (profit is 0, but the algorithm still works)

← Previous
#120 Triangle Next
#122 Best Time to Buy and Sell Stock II →