Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock sounds like a money puzzle. But it is really a pattern question. The interviewer wants to see if you can scan an array once and keep track of the best deal so far. That one-pass idea shows up again and again. So learning it here pays off later.

🎯 The Problem

You get an array of stock prices. You want the biggest profit from one buy and one later sell.

• Each number is the price on one day. The first day is index 0.
• You may buy on one day. Then you sell on a later day.
• You want the largest profit from a single buy and a single sell.
• You must buy before you sell. So the sell day comes after the buy day.
• If no day makes money, the answer is 0.
• The cheapest day seen so far is the minimum price.

Let us say the prices are [7, 1, 5, 3, 6, 4]. The best move is to buy on day 1 at 1. Then sell on day 4 at 6. That gives a profit of 6 - 1 = 5.

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

Explanation: buy on day 1 at price 1, sell on day 4 at price 6, profit = 6 - 1 = 5

Here is the shape of the data. We are looking for the biggest rise from a low day to a later high day.

🐢 Approach 1: Try Every Pair (Brute Force)

The idea in one line: test every buy day against every later sell day.

The idea:

• Pick a buy day.
• Try every later day as the sell day.
• Work out the profit for each pair.
• Keep the biggest profit you find.

How it works:

• One loop picks the buy day.
• A second loop scans every day after it as the sell day.
• Subtract the buy price from each sell price.
• Remember the largest result.

Why it is weak:

• For every day you scan most of the array again.
• Two nested loops over n days means about n times n steps.
• That is O(n²) time. Too slow on a long price list.

Here is the brute-force code for that idea:

def max_profit(prices):
    best = 0

    for buy in range(len(prices)):
        for sell in range(buy + 1, len(prices)):
            profit = prices[sell] - prices[buy]
            best = max(best, profit)

    return best


print(max_profit([7, 1, 5, 3, 6, 4]))

⚡ Approach 2: One Pass Tracking the Lowest Price (Best)

The idea in one line: remember only the cheapest day so far, then check the profit if you sell today.

The idea:

• On any day, the best profit is today's price minus the cheapest day before now.
• So you never need the inner loop.
• You only carry the lowest price seen so far and the best profit so far.

How it works:

• Walk the prices one day at a time.
• Check if selling today beats your best profit. That is today minus lowest.
• If it beats it, update the best profit.
• Then check if today is cheaper than the lowest so far. If yes, update the lowest.
• Profit check comes first, so the buy always sits before the sell.

Why it is fast:

• You touch each day once. That is O(n).
• You store only two numbers. So the extra memory is O(1).

Here is a dry-run on [7, 1, 5, 3, 6, 4]. Watch how the lowest price and best profit change.

Steps to Solve

1. Set the lowest price to the very first price.
2. Set the best profit to 0.
3. Walk through each price one day at a time.
4. Work out today’s profit as current price minus lowest price. If it beats the best profit, update the best profit.
5. If today’s price is below the lowest price, update the lowest price.
6. After the loop, the best profit holds the answer.

#include <stdio.h>

int maxProfit(int prices[], int n) {
    if (n == 0) return 0;
    int minPrice = prices[0];   // cheapest day so far
    int best = 0;               // biggest profit so far
    for (int i = 0; i < n; i++) {
        int profit = prices[i] - minPrice;  // profit if we sell today
        if (profit > best) {
            best = profit;       // found a better deal
        }
        if (prices[i] < minPrice) {
            minPrice = prices[i];  // found a cheaper buy day
        }
    }
    return best;
}

int main(void) {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int n = 6;
    printf("%d\n", maxProfit(prices, n));
    return 0;
}

5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;
    int minPrice = prices[0];  // cheapest day so far
    int best = 0;              // biggest profit so far
    for (int price : prices) {
        best = max(best, price - minPrice);  // profit if we sell today
        minPrice = min(minPrice, price);     // maybe a cheaper buy day
    }
    return best;
}

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

5

public class MaxProfit {
    public static int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int minPrice = prices[0];  // cheapest day so far
        int best = 0;              // biggest profit so far
        for (int price : prices) {
            best = Math.max(best, price - minPrice);  // sell today?
            minPrice = Math.min(minPrice, price);     // cheaper buy day?
        }
        return best;
    }

    public static void main(String[] args) {
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        System.out.println(maxProfit(prices));
    }
}

5

def max_profit(prices):
    if not prices:
        return 0
    min_price = prices[0]       # cheapest day so far
    best = 0                    # biggest profit so far
    for price in prices:
        best = max(best, price - min_price)  # profit if we sell today
        min_price = min(min_price, price)    # maybe a cheaper buy day
    return best


prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))

5

function maxProfit(prices) {
  if (prices.length === 0) return 0;
  let minPrice = prices[0]; // cheapest day so far
  let best = 0;             // biggest profit so far
  for (const price of prices) {
    best = Math.max(best, price - minPrice);  // sell today?
    minPrice = Math.min(minPrice, price);     // cheaper buy day?
  }
  return best;
}

const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices));

5

Let us read the Python version line by line and explain why each line is there.

def max_profit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    best = 0
    for price in prices:
        best = max(best, price - min_price)
        min_price = min(min_price, price)
    return best

The line if not prices guards against an empty list. With no prices there is no trade, so the answer is 0.

The line min_price = prices[0] sets the cheapest day so far to the first price. We have to start somewhere. The first day is the only choice before the loop runs.

The line best = 0 sets the best profit so far to 0. If no deal makes money, 0 is the correct answer. So this is a safe starting value.

The line for price in prices walks through each day once. One pass is all we need, which is why this is O(n).

The line best = max(best, price - min_price) is the heart of the solution. It asks “if I sell today, is the profit bigger than my best so far?” We compute price - min_price because the cheapest buy day is always the best one before today.

The line min_price = min(min_price, price) updates the cheapest day. If today is cheaper than anything before, future days can buy here. The order matters. We check profit first, then update the minimum. That keeps buy strictly before sell.

The final return best gives back the largest profit we found across all days.

⏱️ Time and Space Complexity

The brute force uses two loops, so it is slow but needs no extra memory. The one-pass method scans the array a single time and stores only two numbers. So it is both fast and light. That drops the time from O(n²) all the way to O(n) with O(1) extra space.

🧩 Key Takeaways

• ✅ You only need to remember the lowest price so far, not every past price.
• ✅ At each day, the best sell-today profit is current price minus lowest price.
• ✅ Check the profit first, then update the lowest price, so the buy always comes before the sell.
• ✅ The whole thing runs in O(n) time and O(1) space.
• ✅ If no day makes money, the answer is 0, so start the best profit at 0.

🚀 What’s Next?

• Maximum Product Subarray
• Contains Duplicate