Algorithm Day78 - Best Time to Buy and Sell Stock

Posted on In , Views:

🧩 Problem Description

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 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

1
2
3
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.

Example 2

1
2
3
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done and the max profit = 0.

💡 Intuition

We want the largest difference prices[j] - prices[i] with j > i.
A simple linear scan can track the minimum price so far and compute the potential profit at each day by subtracting the current min from the current price. Keep the maximum profit encountered. This is a greedy O(n) solution.

🔢 Java Code (One-pass Greedy)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) minPrice = price;
            else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
        }
        return maxProfit;
    }
}

🔄 Alternative (Kadane-like)

You can view the problem as finding the maximum subarray sum of daily differences diff[i] = prices[i] - prices[i-1]. Apply Kadane’s algorithm to diff to get the same O(n) result.

⏱ Complexity Analysis

  • Time: O(n) — single pass through prices.
  • Space: O(1) — constant extra memory.

✍️ Summary

  • Track the minimum buying price so far and update the maximum profit at each step.
  • Very efficient greedy solution: O(n) time, O(1) space.

Related problems

  • lc-122 — Best Time to Buy and Sell Stock II
  • lc-123 — Best Time to Buy and Sell Stock III
  • lc-188 — Best Time to Buy and Sell Stock IV