LeetCode 121. Best Time to Buy and Sell Stock

LeetCode 121. Best Time to Buy and Sell Stock

LINK: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Matter

You are given a list of daily stock prices.

Your goal is to determine the best possible profit by performing exactly one buy and one sell operation, where the sell must occur after the buy.

If no profitable transaction exists, return 0.

Example.

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

Output:
5

Explanation:
Buy at 1 and sell at 6, resulting in a profit of 5.

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

Output:
0

Explanation:
The price continuously decreases, so no profit can be made.

Constraints

1 <= prices.length <= $10^5$

0 <= prices[i] <= $10^4$

Problem analysis

The key idea is:

At each step, calculate the profit assuming you sell today and bought at the lowest price seen so far.

This avoids checking all possible pairs.

Approach

• Track the minimum price encountered so far
• Compute profit for each day
• Keep updating the maximum profit

❌ Inefficient Approach

• Checking all pairs → $O(n^2)$ → too slow
• Sorting → invalid because order matters

Miss Check list

• Buying must happen before selling
• Ignore negative profits
• Always compare with previous minimum price
• Only one transaction is allowed

Solution

Greedy + Single Pass

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int min_price = INT_MAX;
        int max_profit = 0;

        for (int price : prices) 
        {
            min_price = std::min(min_price, price);
            max_profit = std::max(max_profit, price - min_price);
        }

        return max_profit;
    }
};

class Solution 
{
public:
    int maxProfit(std::vector<int>& prices) 
    {
        std::vector<int> vctResults;
        vctResults.push_back(0);

        int i32Size = (int)prices.size();
        int i32MinCursor = prices[0];
        int i32MaxCursor = prices[0];

        for(int i = 0; i < i32Size - 1; ++i)
        {
            int i32Cur = prices[i];
            int i32CurNext = prices[i+1];

            if(i32MaxCursor < i32Cur)
                i32MaxCursor = i32Cur;

            if(i32MinCursor > i32CurNext)
            {
                vctResults.push_back(i32MaxCursor - i32MinCursor);
                i32MinCursor = i32CurNext;
                i32MaxCursor = i32CurNext;
            }
        }

        int i32Cur = prices[i32Size-1];

        if(i32MaxCursor < i32Cur)
            i32MaxCursor = i32Cur;

        vctResults.push_back(i32MaxCursor - i32MinCursor);

        std::vector<int>::iterator itResult = std::max_element(vctResults.begin(), vctResults.end());

        return *itResult;
    }
};