Skip to main content

šŸŸ© Best Time to Buy and Sell Stock (#121)

šŸ”— Problem Linkā€‹

šŸ“‹ Problem Statementā€‹

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

šŸ’” Examplesā€‹

Example 1ā€‹

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Example 2ā€‹

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No profit can be made, so return 0.

šŸ”‘ Key Insights & Approachā€‹

Core Observation: Track minimum price seen so far, calculate profit at each step.

Why Single Pass?

  • Only need to know minimum price before current day
  • Can calculate max profit in O(n) time
  • No need to look ahead

Approaches:

  1. Brute force all pairs: O(nĀ²)
  2. Track min price and max profit: O(n) - optimal

Pattern: "Sliding Window / One Pass" pattern tracking minimum and maximum.

šŸ Solution: Pythonā€‹

Approach: Track Min Priceā€‹

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

from typing import List

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:
            # Update minimum price seen so far
            min_price = min(min_price, price)

            # Calculate profit if sold today
            profit = price - min_price

            # Update maximum profit
            max_profit = max(max_profit, profit)

        return max_profit

Approach 2: Two Pointers (Buy/Sell)ā€‹

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

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0  # Buy pointer
        right = 1  # Sell pointer
        max_profit = 0

        while right < len(prices):
            # Profitable transaction?
            if prices[left] < prices[right]:
                profit = prices[right] - prices[left]
                max_profit = max(max_profit, profit)
            else:
                # Found lower buy price
                left = right

            right += 1

        return max_profit

šŸ”µ Solution: Golangā€‹

Approach: Track Min Priceā€‹

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

import "math"

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    minPrice := math.MaxInt32
    maxProfit := 0

    for _, price := range prices {
        // Update minimum price
        if price < minPrice {
            minPrice = price
        }

        // Calculate profit
        profit := price - minPrice
        if profit > maxProfit {
            maxProfit = profit
        }
    }

    return maxProfit
}

šŸ“š Referencesā€‹