Code Logo

Best Time to Buy and Sell Stock

Published at24 Jul 2026
Created by
Easy 0 views
Like0

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 future day to sell it. Return the maximum profit you can achieve from this transaction. If no profit is possible, return 0.

This is a classic one-pass DP problem. The key insight is to track the minimum price seen so far and the maximum profit achievable at each step. As we iterate through prices, we update the minimum price if the current price is lower. We also calculate the profit if we sold at the current price (current price minus minimum price) and update the maximum profit if this is higher.

At any point, the minimum price so far represents the best buying opportunity we have seen. The profit calculation represents the profit if we sold today. The maximum profit variable keeps the best profit across all days. This O(n) algorithm uses only O(1) extra space.

Edge cases include a single day (no transaction possible, return 0), a strictly decreasing price (no profit possible, return 0), and equal prices throughout (no profit, return 0).

The one-pass DP approach works because the optimal solution only needs the minimum price seen so far. This is a simple example of stateful DP where only one variable (min price) captures all necessary information from previous states.

Example Input & Output

Example 1
Input
[7,6,4,3,1]
Output
0
Explanation

Decreasing prices, no profit possible.

Example 2
Input
[1,2]
Output
1
Explanation

Buy at 1, sell at 2.

Example 3
Input
[3,3,3]
Output
0
Explanation

Equal prices, no profit.

Example 4
Input
[7,1,5,3,6,4]
Output
5
Explanation

Buy at 1 (day 2), sell at 6 (day 5), profit 5.

Example 5
Input
[1]
Output
0
Explanation

Only one price, no transaction.

Algorithm Flow

Recommendation Algorithm Flow for Best Time to Buy and Sell Stock

Solution Approach

Track the minimum price seen so far and the maximum profit achievable at each step. As you iterate through the prices array, update the minimum price whenever a lower price is found. For each price, the potential profit is the current price minus the minimum price so far. Keep track of the maximum profit seen.

function maxProfit(prices) {
  var minPrice = prices[0], maxProfit = 0;
  for (var i = 1; i < prices.length; i++) {
    if (prices[i] < minPrice) minPrice = prices[i];
    var profit = prices[i] - minPrice;
    if (profit > maxProfit) maxProfit = profit;
  }
  return maxProfit;
}

This single-pass approach works because the optimal buy day is always the lowest price seen before the sell day. By tracking the minimum price as we go, we can compute the best possible profit for each potential sell day without nested loops.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) minPrice = prices[i];
            int profit = prices[i] - minPrice;
            if (profit > maxProfit) maxProfit = profit;
        }
        return maxProfit;
    }
}