LeetCode Solutions Blog

Best Time to Buy and Sell Stock

Number: 121

Difficulty: Easy

Paid? No

Problem Description

Given an array of stock prices where prices[i] is the price on the ith day, determine the maximum profit achievable by buying on one day and selling on a later day. If no profit is possible, return 0.

Key Insights

Traverse the list of prices once while keeping track of the minimum price encountered so far.
At each day, calculate the profit if you sold the stock on that day.
Update the maximum profit when the current profit exceeds the previous maximum.
The optimal solution makes a single pass through the array with constant space usage.

Space and Time Complexity

Time Complexity: O(n) - requires one pass through the prices array. Space Complexity: O(1) - only a few extra variables are used.

Solution

We solve the problem using a simple linear scan. We maintain two key variables: one for the minimum price seen so far and another for the maximum profit calculated so far. As we iterate, we continuously update the minimum price if a lower price is found, and then compute the potential profit at the current price. If this profit exceeds the current maximum profit, we update the maximum profit. The final maximum profit is returned after iterating through all prices.

Code Solutions

def maxProfit(prices):
    # Initialize min_price as infinity and max_profit as 0
    min_price = float('inf')
    max_profit = 0
    # Iterate through each price in the list
    for price in prices:
        # Update the minimum price if current price is lower
        if price < min_price:
            min_price = price
        else:
            # Calculate current profit and update max_profit if it is higher
            max_profit = max(max_profit, price - min_price)
    return max_profit

# Example usage:
# result = maxProfit([7,1,5,3,6,4])
# print(result)  # Output should be 5