Skip to main content
CodePeetCodePeet
BLIND 75

Best Time to Buy and Sell Stock

EASYProblemSolveExternal Links

Description

You are given an array prices where prices[i] represents the price of a stock on the i-th day.

You want to maximize your profit by choosing a single day to buy the stock and a different day in the future to sell it. You can only complete at most one transaction (one buy and one sell).

Return the maximum profit you can achieve. If no profit is possible (the stock price only decreases), return 0.

Note that you cannot sell before you buy — the sell day must come strictly after the buy day.

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: The stock price strictly decreases every day. No matter which day we buy, every future day has a lower price. There is no way to make a profit, so we return 0.

Constraints

  • 1 ≤ prices.length ≤ 10⁵
  • 0 ≤ prices[i] ≤ 10⁴

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to consider every possible pair of buy and sell days, then return the maximum profit found.

For each day i (the buy day), we look at every future day j > i (the sell day) and compute the profit prices[j] - prices[i]. We keep track of the maximum profit seen across all valid pairs.

This is like trying on every possible combination of outfits — exhaustive but slow. You check every single (buy, sell) pair without any cleverness or shortcuts.

Why does this work? Because by examining every valid pair, we guarantee that the optimal pair is included somewhere in our search. We're leaving no stone unturned.

The downside is obvious: with n days, there are roughly n²/2 pairs to check, giving O(n²) time complexity. For n = 100,000, that's ~5 billion operations — far too slow.

Step-by-Step Explanation

Let's trace through prices = [7, 1, 5, 3, 6, 4]:

Step 1: Initialize maxProfit = 0.

Step 2: Buy day i=0 (price=7). Check sell days: j=1 (1-7=-6), j=2 (5-7=-2), j=3 (3-7=-4), j=4 (6-7=-1), j=5 (4-7=-3). All negative — no profit possible buying at 7.

Step 3: Buy day i=1 (price=1). Check sell days: j=2 (5-1=4, maxProfit=4), j=3 (3-1=2), j=4 (6-1=5, maxProfit=5), j=5 (4-1=3). Best from this buy day is 5.

Step 4: Buy day i=2 (price=5). Check sell days: j=3 (3-5=-2), j=4 (6-5=1), j=5 (4-5=-1). No improvement.

Step 5: Buy day i=3 (price=3). Check sell days: j=4 (6-3=3), j=5 (4-3=1). No improvement.

Step 6: Buy day i=4 (price=6). Check sell days: j=5 (4-6=-2). No improvement.

Result: maxProfit = 5 (buy at day 1, sell at day 4).

Brute Force — Check All Buy-Sell Pairs — Watch how the brute force approach checks every (buy, sell) pair. Two nested loops explore all combinations where buy day < sell day, tracking the maximum profit found so far.

Algorithm

  1. Initialize maxProfit = 0
  2. For each day i from 0 to n-2 (buy day):
    • For each day j from i+1 to n-1 (sell day):
      • Calculate profit = prices[j] - prices[i]
      • If profit > maxProfit, update maxProfit = profit
  3. Return maxProfit

Code

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        int n = prices.size();

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

        return maxProfit;
    }
};
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        n = len(prices)

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

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

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

        return maxProfit;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n-1 times, and for each iteration, the inner loop runs up to n-1 times. Total comparisons = n(n-1)/2, which is O(n²). For n = 100,000, this is approximately 5 × 10⁹ operations — too slow for the given constraints.

Space Complexity: O(1)

We only use a constant amount of extra space for the maxProfit variable and loop counters. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity, which is far too slow when n can be up to 100,000. With ~5 billion operations, it would time out on any online judge.

The fundamental waste is redundant computation. When we move from buy day i to buy day i+1, we throw away everything we learned about future prices and scan them all again from scratch.

The key insight: to maximize profit, we need the smallest buy price seen so far and the largest sell price after that buy. We don't need to check every pair — we just need to track the minimum price as we scan left to right. At each position, the maximum profit achievable by selling today is simply today's price - minimum price so far.

This transforms the problem from "find the best pair" (O(n²)) to "track one running minimum" (O(n)).

Optimal Approach - One Pass with Running Minimum

Intuition

Instead of checking every pair, we make a single pass through the array while maintaining two things:

  1. minPrice — the lowest stock price we've seen so far (the best buy opportunity up to this point)
  2. maxProfit — the best profit achievable so far

As we visit each day's price:

  • If today's price is lower than minPrice, we update minPrice — we've found a better day to buy
  • Otherwise, we calculate the profit of selling today (today's price - minPrice) and update maxProfit if it's better

Why does this work? Because the maximum profit must come from some buy-sell pair (i, j) where i < j. As we scan left to right, minPrice always holds the smallest value in prices[0..current], which is the best possible buy price. So for each sell day, we only need to compare against this one best buy price — not all previous prices.

Think of it like hiking through a valley. As you walk, you remember the lowest point you've been to (minPrice). At each new position, you calculate how high you've climbed relative to that lowest point (current profit). The highest climb you record is the answer.

Step-by-Step Explanation

Let's trace through prices = [7, 1, 5, 3, 6, 4]:

Step 1: Initialize minPrice = ∞, maxProfit = 0.

Step 2: Day 0, price = 7. 7 < ∞, so update minPrice = 7. Profit = 7 - 7 = 0. maxProfit stays 0.

Step 3: Day 1, price = 1. 1 < 7, so update minPrice = 1. Profit = 1 - 1 = 0. maxProfit stays 0.

Step 4: Day 2, price = 5. 5 > 1, not a new minimum. Profit = 5 - 1 = 4. Update maxProfit = 4.

Step 5: Day 3, price = 3. 3 > 1, not a new minimum. Profit = 3 - 1 = 2. maxProfit stays 4.

Step 6: Day 4, price = 6. 6 > 1, not a new minimum. Profit = 6 - 1 = 5. Update maxProfit = 5.

Step 7: Day 5, price = 4. 4 > 1, not a new minimum. Profit = 4 - 1 = 3. maxProfit stays 5.

Result: maxProfit = 5. One pass, 6 steps, O(n) time.

Optimal — Single Pass with Running Minimum — Watch how a single left-to-right scan tracks the minimum price and computes profit at each step. No nested loops — just one pointer sweeping through the array.

Algorithm

  1. Initialize minPrice = ∞ (or the first element) and maxProfit = 0
  2. For each price in the array:
    • If price < minPrice, update minPrice = price (found a better buy day)
    • Otherwise, compute profit = price - minPrice
      • If profit > maxProfit, update maxProfit = profit
  3. Return maxProfit

Code

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

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;
    }
};
from typing import List

class Solution:
    def maxProfit(self, 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
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;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make exactly one pass through the array, visiting each element once. Each visit performs O(1) work (a comparison and possibly an update). Total: n iterations × O(1) work = O(n).

This is optimal — any solution must examine every price at least once, so O(n) is a lower bound.

Space Complexity: O(1)

We only maintain two variables: minPrice and maxProfit. No additional data structures, no recursion. Constant extra space regardless of input size.

This is both time-optimal and space-optimal — you cannot do better than O(n) time and O(1) space for this problem.