LeetCode 121: Best Time To Buy And Sell Stock — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Easy — Array | Dynamic Programming | Greedy

The Problem

Find the maximum profit you can achieve by buying a stock on one day and selling it on a later day. You can only complete at most one transaction (buy once and sell once).

Approach

Use a single pass approach to track the minimum price seen so far and calculate the maximum profit at each step. For each price, update the minimum price and check if selling at the current price would yield a higher profit than previously calculated.

Time: O(n) · Space: O(1)

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        min_price = float("inf")
        max_profit = 0

        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)

        return max_profit