Best Time to Buy and Sell Stock

easy
Sliding WindowArrayDynamic ProgrammingSliding Window

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.

Examples

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 <= 10^5
  • 0 <= prices[i] <= 10^4

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

The simplest approach is to consider every possible pair of buy and sell days. For each day, we look at all future days and calculate the profit. We keep track of the maximum profit seen across all pairs. While correct, this approach is too slow for large inputs due to the nested loops.

Algorithm

  1. Initialize maxProfit to 0.
  2. Use an outer loop to iterate over each possible buy day i from 0 to n-2.
  3. Use an inner loop to iterate over each possible sell day j from i+1 to n-1.
  4. Calculate profit = prices[j] - prices[i]. If profit > maxProfit, update maxProfit.
  5. Return maxProfit.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
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];
                maxProfit = max(maxProfit, profit);
            }
        }

        return maxProfit;
    }
};
Java 21
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];
                maxProfit = Math.max(maxProfit, profit);
            }
        }

        return maxProfit;
    }
}
Python 3.12
def maxProfit(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]
            max_profit = max(max_profit, profit)

    return max_profit
Go 1.26
func maxProfit(prices []int) int {
    maxP := 0
    for i := 0; i < len(prices); i++ {
        for j := i + 1; j < len(prices); j++ {
            profit := prices[j] - prices[i]
            if profit > maxP {
                maxP = profit
            }
        }
    }
    return maxP
}
Approach 2

Single Pass (Kadane's Variant)

Intuition

The key insight is that to maximize profit, we want to buy at the lowest price seen so far and sell at the current price. As we scan from left to right, we maintain the minimum price encountered. At each day, the best profit we could make by selling today is the current price minus the minimum price so far. We track the maximum of all these potential profits. This works because the minimum price is always to the left of (or at) the current position, satisfying the buy-before-sell constraint. This is essentially a sliding window where the left boundary jumps to a new minimum whenever one is found.

Algorithm

  1. Initialize minPrice to Infinity (or the first price) and maxProfit to 0.
  2. Iterate through each price in the array.
  3. If the current price is less than minPrice, update minPrice to the current price.
  4. Otherwise, calculate profit = currentPrice - minPrice. If profit > maxProfit, update maxProfit.
  5. Return maxProfit after the loop.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else {
                maxProfit = max(maxProfit, price - minPrice);
            }
        }

        return maxProfit;
    }
};
Java 21
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 {
                maxProfit = Math.max(maxProfit, price - minPrice);
            }
        }

        return maxProfit;
    }
}
Python 3.12
def maxProfit(prices: list[int]) -> int:
    min_price = float("inf")
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)

    return max_profit
Go 1.26
func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxP := 0
    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else if price-minPrice > maxP {
            maxP = price - minPrice
        }
    }
    return maxP
}

Frequently asked questions

What is the optimal time complexity of Best Time to Buy and Sell Stock?

The most efficient approach in this guide ("Single Pass (Kadane's Variant)") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Best Time to Buy and Sell Stock use?

Best Time to Buy and Sell Stock is a easy-level Sliding Window problem involving Array, Dynamic Programming, Sliding Window. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Best Time to Buy and Sell Stock be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Contains Duplicate

Original problem: leetcode.com

Loading editor...
Input
prices=
[7,1,5,3,6,4]
Expected Output
5