Best Time to Sell Stock

Dynamic Programming Easy

Python Java C++

def maxProfit(prices):
    # Track minimum price and maximum profit
    minPrice = float('inf')
    profit = 0
    
    for price in prices:
        minPrice = min(price, minPrice)
        profit = max(profit, price - minPrice)
        
    return profit

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int profit = 0;
        
        for (int price : prices) {
            minPrice = Math.min(price, minPrice);
            profit = Math.max(profit, price - minPrice);
        }
        
        return profit;
    }
}

class Solution {
public:
    int maxProfit(vector& prices) {
        int minPrice = INT_MAX;
        int profit = 0;
        
        for (int price : prices) {
            minPrice = min(price, minPrice);
            profit = max(profit, price - minPrice);
        }
        
        return profit;
    }
};

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.

Detailed Explanation

Approach

The solution uses Kadane's algorithm principle but simplified for this specific case. We track two values: the minimum price seen so far and the maximum profit possible. For each price, we update both these values.

Key Concepts

1. Minimum Price Tracking: Keep track of the lowest price we've seen so far
2. Profit Calculation: At each step, calculate potential profit using current price minus minimum price seen
3. Maximum Profit: Update maximum profit if current potential profit is greater

Algorithm Steps

1. Initialize minPrice as maximum possible value
2. Initialize profit as 0
3. For each price in the array:
   • Update minPrice if current price is lower
   • Calculate potential profit (current price - minPrice)
   • Update maximum profit if potential profit is higher

Visual Example

Input: prices = [7,1,5,3,6,4] Step by step: 7: minPrice = 7, profit = 0 (first price) 1: minPrice = 1, profit = 0 (new minimum) 5: minPrice = 1, profit = 4 (5 - 1 = 4) 3: minPrice = 1, profit = 4 (3 - 1 = 2, keep old profit) 6: minPrice = 1, profit = 5 (6 - 1 = 5) 4: minPrice = 1, profit = 5 (4 - 1 = 3, keep old profit) Output: 5 (buy at 1, sell at 6)

Time and Space Complexity

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only using two variables

Why This Works

For any given selling day, the best profit would come from buying at the minimum price seen before that day. By tracking the minimum price, we can calculate the best possible profit for each selling day in a single pass.

Edge Cases

• Array length = 1: Return 0 (can't buy and sell same day)
• Prices always decreasing: Return 0 (no profit possible)
• Single value repeated: Return 0
• Empty array: Return 0

Common Mistakes

• Not handling empty or single-element arrays
• Trying to track buy and sell dates unnecessarily
• Using nested loops (O(n²) solution)
• Not considering that you must buy before selling