121. Best Time to Buy And Sell Stock - Explanation

Problem Link

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


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

Google28 Meta24 Amazon17 Microsoft15 Bloomberg8 IBM7 Tesla4 Apple3 Citadel3 SAP3 Agoda7 Tiktok4 Deloitte3 TCS3 Zoho3 NVIDIA3 Akamai3 Zoox3 J.P. Morgan2 Adobe2 Uber23 Goldman Sachs20 Morgan Stanley17 Accenture16 Bolt11 Infosys9 Oracle8 Walmart Labs9 Visa9 PayPal8


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

  1. Initialize res = 0 to store the maximum profit.
  2. Loop through each day i as the buy day.
  3. For each buy day, loop through each day j > i as the sell day.
  4. Calculate the profit prices[j] - prices[i] and update res.
  5. 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

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)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

  1. Set two pointers:
    • l = 0 (buy day)
    • r = 1 (sell day)
    • maxP = 0 to track maximum profit
  2. 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.
  3. 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

Time & Space Complexity

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

3. Dynamic Programming

Intuition

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

  1. The lowest price so far → this is the best day to buy.
  2. 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

  1. Initialize:
    • minBuy as the first price,
    • maxP = 0 for the best profit.
  2. Loop through each price sell:
    • Update maxP with sell - minBuy.
    • Update minBuy if we find a smaller price.
  3. 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

Time & Space Complexity

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