Best Time to Buy and Sell Stock

Stock Prices

Current Day

Current Price

Min Price (Buy)

Day: -

Max Profit

Sell Day: -

Potential Profit: -

Click "Step" or "Play" to start the visualization

Current Day

Min Price (Buy)

Best Sell Day

Python Code

                profit = 0
            
                mini = prices[0]
            
                for i in range(1, len(prices)):
            
                    cost = prices[i] - mini
            
                    profit = max(profit, cost)
            
                    mini = min(mini, prices[i])
            
                return profit

Complexity Analysis

Time Complexity O(n) Space Complexity O(1)

Time Complexity: O(n)

Breakdown

Single iteration through n price values
Each iteration: compute profit, update minimum
Two comparisons per element: O(1)
No nested loops or lookbacks

T(n) = n × O(1) = O(n)

Mathematical Intuition

The brute force checks all n(n-1)/2 pairs (i, j) where i < j. The optimization: for any sell day j, the optimal buy day is argmin(prices[0..j-1]). Since this minimum only depends on previous elements, we track it incrementally—avoiding repeated scans.

Key Insight

This is equivalent to finding the maximum difference between a peak and its preceding valley in a sequence—a classic prefix minimum pattern.

Space Complexity: O(1)

Breakdown

minPrice: tracks minimum seen so far
maxProfit: tracks best profit found
No arrays or data structures allocated
Input array is read-only

S(n) = O(1) — two scalar variables

Mathematical Intuition

We only need the running minimum, not the full prefix minimum array. This "online" property means we can process prices as a stream, discarding each value after extracting its information.

Key Insight

The problem has the "prefix property": the answer at position j depends only on prices[0..j], enabling single-pass processing with constant memory.