Leetcode 121 - Best Time to Buy and Sell Stock

Table of contents

Problem

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 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.

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: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Explanation/Approach

The goal is to find the maximum difference between two numbers in the array where the larger number comes after the smaller one. This represents the maximum profit.

• One-pass Approach: Iterate through the array, updating the minimum price so far and the maximum profit at each step.

Solution: One-pass Approach

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')  # Initialize min price to infinity
        max_profit = 0  # Initialize max profit to 0

        # Iterate over the prices
        for price in prices:
            # Update the min price if the current price is lower
            min_price = min(min_price, price)
            # Update the max profit if the current profit is higher
            max_profit = max(max_profit, price - min_price)

        return max_profit

Time and Memory Complexity

The time complexity is O(n), where n is the number of days, as we only iterate through the list once. The space complexity is O(1) since we only use two variables regardless of the input size.

Explanation

The algorithm maintains two variables: min_price, which represents the lowest price seen so far, and max_profit, the highest profit that can be made by selling at the current price. For each price in the list, it checks if the current price is lower than the min_price and updates it. Then, it calculates the profit that could be made by selling at the current price and updates max_profit if this profit is higher than the current max_profit. The final value of max_profit is the answer.