121. Best Time to Buy And Sell Stock - Explanation

Description

You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.

You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.

Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.

Example 1:

Input: prices = [10,1,5,6,7,1]

Output: 6

Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.

Example 2:

Input: prices = [10,8,7,5,2]

Output: 0

Explanation: No profitable transactions can be made, thus the max profit is 0.

Constraints:

1 <= prices.length <= 100
0 <= prices[i] <= 100

Topics

Array Dynamic Programming

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to iterate through the array with index i, considering it as the day to buy, and trying all possible options for selling it on the days to the right of index i. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

You should buy at a price and always sell at a higher price. Can you iterate through the array with index i, considering it as either the buying price or the selling price?

Hint 3

We can iterate through the array with index i, considering it as the selling value. But what value will it be optimal to consider as buying point on the left of index i?

Hint 4

We are trying to maximize profit = sell - buy. If the current i is the sell value, we want to choose the minimum buy value to the left of i to maximize the profit. The result will be the maximum profit among all. However, if all profits are negative, we can return 0 since we are allowed to skip doing transaction.

Company Tags

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Iterating through elements and tracking values
Two Pointers - Using multiple pointers to track buy and sell positions
Greedy Algorithms - Making locally optimal choices (tracking minimum buy price) for global optimization

1. Brute Force

Intuition

The brute-force approach checks every possible buy–sell pair.
For each day, we pretend to buy the stock, and then we look at all the future days to see what the best selling price would be.
Among all these profits, we keep the highest one.

Algorithm

Initialize res = 0 to store the maximum profit.
Loop through each day i as the buy day.
For each buy day, loop through each day j > i as the sell day.
Calculate the profit prices[j] - prices[i] and update res.
Return res after checking all pairs.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices)):
            buy = prices[i]
            for j in range(i + 1, len(prices)):
                sell  = prices[j]
                res = max(res, sell - buy)
        return res

public class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 0; i < prices.length; i++) {
            int buy = prices[i];
            for (int j = i + 1; j < prices.length; j++) {
                int sell = prices[j];
                res = Math.max(res, sell - buy);
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 0; i < prices.size(); i++) {
            int buy = prices[i];
            for (int j = i + 1; j < prices.size(); j++) {
                int sell = prices[j];
                res = max(res, sell - buy);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} prices
     * @return {number}
     */
    maxProfit(prices) {
        let res = 0;
        for (let i = 0; i < prices.length; i++) {
            let buy = prices[i];
            for (let j = i + 1; j < prices.length; j++) {
                let sell = prices[j];
                res = Math.max(res, sell - buy);
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxProfit(int[] prices) {
        int res = 0;
        for (int i = 0; i < prices.Length; i++) {
            int buy = prices[i];
            for (int j = i + 1; j < prices.Length; j++) {
                int sell = prices[j];
                res = Math.Max(res, sell - buy);
            }
        }
        return res;
    }
}

func maxProfit(prices []int) int {
    res := 0
    for i := 0; i < len(prices); i++ {
        buy := prices[i]
        for j := i + 1; j < len(prices); j++ {
            sell := prices[j]
            res = max(res, sell - buy)
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var res = 0
        for (i in prices.indices) {
            val buy = prices[i]
            for (j in i + 1 until prices.size) {
                val sell = prices[j]
                res = maxOf(res, sell - buy)
            }
        }
        return res
    }
}

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var res = 0
        for i in 0..<prices.count {
            let buy = prices[i]
            for j in (i + 1)..<prices.count {
                let sell = prices[j]
                res = max(res, sell - buy)
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Two Pointers

Intuition

We want to buy at a low price and sell at a higher price that comes after it.
Using two pointers helps us track this efficiently:

l is the buy day (looking for the lowest price)
r is the sell day (looking for a higher price)

If the price at r is higher than at l, we can make a profit — so we update the maximum.
If the price at r is lower, then r becomes the new l because a cheaper buying price is always better.

By moving the pointers this way, we scan the list once and always keep the best buying opportunity.

Algorithm

Set two pointers:
- l = 0 (buy day)
- r = 1 (sell day)
- maxP = 0 to track maximum profit
While r is within the array:
- If prices[r] > prices[l], compute the profit and update maxP.
- Otherwise, move l to r (we found a cheaper buy price).
- Move r to the next day.
Return maxP at the end.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        maxP = 0

        while r < len(prices):
            if prices[l] < prices[r]:
                profit = prices[r] - prices[l]
                maxP = max(maxP, profit)
            else:
                l = r
            r += 1
        return maxP

public class Solution {
    public int maxProfit(int[] prices) {
        int l = 0, r = 1;
        int maxP = 0;

        while (r < prices.length) {
            if (prices[l] < prices[r]) {
                int profit = prices[r] - prices[l];
                maxP = Math.max(maxP, profit);
            } else {
                l = r;
            }
            r++;
        }
        return maxP;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int l = 0, r = 1;
        int maxP = 0;

        while (r < prices.size()) {
            if (prices[l] < prices[r]) {
                int profit = prices[r] - prices[l];
                maxP = max(maxP, profit);
            } else {
                l = r;
            }
            r++;
        }
        return maxP;
    }
};

class Solution {
    /**
     * @param {number[]} prices
     * @return {number}
     */
    maxProfit(prices) {
        let l = 0,
            r = 1;
        let maxP = 0;

        while (r < prices.length) {
            if (prices[l] < prices[r]) {
                let profit = prices[r] - prices[l];
                maxP = Math.max(maxP, profit);
            } else {
                l = r;
            }
            r++;
        }
        return maxP;
    }
}

public class Solution {
    public int MaxProfit(int[] prices) {
        int l = 0, r = 1;
        int maxP = 0;

        while (r < prices.Length) {
            if (prices[l] < prices[r]) {
                int profit = prices[r] - prices[l];
                maxP = Math.Max(maxP, profit);
            } else {
                l = r;
            }
            r++;
        }
        return maxP;
    }
}

func maxProfit(prices []int) int {
    l, r := 0, 1
    maxP := 0

    for r < len(prices) {
        if prices[l] < prices[r] {
            profit := prices[r] - prices[l]
            if profit > maxP {
                maxP = profit
            }
        } else {
            l = r
        }
        r++
    }
    return maxP
}

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var l = 0
        var r = 1
        var maxP = 0

        while (r < prices.size) {
            if (prices[l] < prices[r]) {
                val profit = prices[r] - prices[l]
                maxP = maxOf(maxP, profit)
            } else {
                l = r
            }
            r++
        }
        return maxP
    }
}

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var l = 0, r = 1
        var maxP = 0

        while r < prices.count {
            if prices[l] < prices[r] {
                let profit = prices[r] - prices[l]
                maxP = max(maxP, profit)
            } else {
                l = r
            }
            r += 1
        }
        return maxP
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Dynamic Programming

Intuition

As we scan through the prices, we keep track of two things:

The lowest price so far → this is the best day to buy.
The best profit so far → selling today minus the lowest buy price seen earlier.

At each price, we imagine selling on that day.
The profit would be:
current price – lowest price seen so far

We then update:

the maximum profit,
and the lowest price if we find a cheaper one.

This way, we make the optimal buy–sell decision in one simple pass.

Algorithm

Initialize:
- minBuy as the first price
- maxP = 0 for the best profit
Loop through each price sell:
- Update maxP with sell - minBuy.
- Update minBuy if we find a smaller price.
Return maxP after scanning all days.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxP = 0
        minBuy = prices[0]

        for sell in prices:
            maxP = max(maxP, sell - minBuy)
            minBuy = min(minBuy, sell)
        return maxP

public class Solution {
    public int maxProfit(int[] prices) {
        int maxP = 0;
        int minBuy = prices[0];

        for (int sell : prices) {
            maxP = Math.max(maxP, sell - minBuy);
            minBuy = Math.min(minBuy, sell);
        }
        return maxP;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxP = 0;
        int minBuy = prices[0];

        for (int& sell : prices) {
            maxP = max(maxP, sell - minBuy);
            minBuy = min(minBuy, sell);
        }
        return maxP;
    }
};

class Solution {
    /**
     * @param {number[]} prices
     * @return {number}
     */
    maxProfit(prices) {
        let maxP = 0;
        let minBuy = prices[0];

        for (let sell of prices) {
            maxP = Math.max(maxP, sell - minBuy);
            minBuy = Math.min(minBuy, sell);
        }
        return maxP;
    }
}

public class Solution {
    public int MaxProfit(int[] prices) {
        int maxP = 0;
        int minBuy = prices[0];

        foreach (int sell in prices) {
            maxP = Math.Max(maxP, sell - minBuy);
            minBuy = Math.Min(minBuy, sell);
        }
        return maxP;
    }
}

func maxProfit(prices []int) int {
    maxP := 0
    minBuy := math.MaxInt32

    for _, sell := range prices {
        if sell - minBuy > maxP {
            maxP = sell - minBuy
        }
        if sell < minBuy {
            minBuy = sell
        }
    }
    return maxP
}

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var maxP = 0
        var minBuy = Int.MAX_VALUE

        for (sell in prices) {
            maxP = maxOf(maxP, sell - minBuy)
            minBuy = minOf(minBuy, sell)
        }
        return maxP
    }
}

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var maxP = 0
        var minBuy = prices[0]

        for sell in prices {
            maxP = max(maxP, sell - minBuy)
            minBuy = min(minBuy, sell)
        }
        return maxP
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Selling Before Buying

The sell day must come after the buy day. Calculating prices[i] - prices[j] where j > i means you're selling in the past, which is invalid.

# Wrong: selling before buying
for i in range(len(prices)):
    for j in range(i):  # j < i means selling earlier
        profit = prices[j] - prices[i]  # Backwards

Returning Negative Profit

If prices only decrease, the maximum profit is 0 (don't trade), not a negative number. Always ensure the result is at least 0.

# Wrong: can return negative
return maxPrice - minPrice  # Could be negative if maxPrice found before minPrice