Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0121 - Best Time to Buy and Sell Stock
    0121 - Best Time to Buy and Sell Stock
    0121 - Best Time to Buy and Sell Stock
    0121 - Best Time to Buy and Sell Stock

    0121 - Best Time to Buy and Sell Stock

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

    Solution 1 - Brute Force

    Iterate through every pair of days using two nested loops. For each pair, compute the profit from buying on the earlier day and selling on the later day. Track and return the maximum profit found.

    TimeComplexity:O(n2)TimeComplexity: O(n^2)TimeComplexity:O(n2)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Single Pass (Track Minimum Price)

    Traverse the array once, keeping track of the minimum price seen so far. At each step, compute the profit if selling at the current price and update the maximum profit accordingly.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 3 - Two Pointers

    Use a left pointer (buy day) and a right pointer (sell day). If the sell price is higher than the buy price, calculate the profit and update the maximum. Otherwise, move the buy pointer to the current sell day since we found a cheaper price. Always advance the sell pointer.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0121.1 - Best Time to Buy and Sell Stock - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def maxProfit(self, prices: List[int]) -> int:
        """Max Profit Function"""
        res = 0

        for i in range(len(prices) - 1):
            for j in range(i + 1, len(prices)):
                res = max(res, prices[j] - prices[i])

        return res


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().maxProfit([7, 1, 5, 3, 6, 4]))  # 5
    print(Solution().maxProfit([7, 6, 4, 3, 1]))      # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0121.2 - Best Time to Buy and Sell Stock - Solution 2 - Single Pass (Track Minimum Price) """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def maxProfit(self, prices: List[int]) -> int:
        """Max Profit Function"""
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price

        return max_profit


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().maxProfit([7, 1, 5, 3, 6, 4]))  # 5
    print(Solution().maxProfit([7, 6, 4, 3, 1]))      # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0121.3 - Best Time to Buy and Sell Stock - Solution 3 - Two Pointers """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def maxProfit(self, prices: List[int]) -> int:
        """Max Profit Function"""
        l, r = 0, 1
        max_profit = 0

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

        return max_profit


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().maxProfit([7, 1, 5, 3, 6, 4]))  # 5
    print(Solution().maxProfit([7, 6, 4, 3, 1]))      # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()