NUHMAN.com

Introduction

LeetCode 121: Best Time to Buy and Sell Stock is a popular problem that requires finding the maximum profit you can achieve by buying and selling a stock, where the price of the stock is given for each day in an array. The goal is to buy at a lower price and sell at a higher price after the buy day.

To solve this problem efficiently, we can use a greedy algorithm with a one-pass approach, which ensures an optimal solution in O(n) time and O(1) space.

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.

Example:

go

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.

Approach:

Greedy Approach:

The optimal strategy to maximize profit is simple: buy the stock at the lowest price encountered so far and sell it at the current price to achieve the maximum profit.

1. Track the minimum price: As we iterate through the prices, we keep track of the lowest price seen so far.
2. Calculate the potential profit: For each price, calculate the profit if we had bought the stock at the lowest price so far and sold it at the current price.
3. Update the maximum profit: Keep track of the maximum profit encountered during the iteration.

The idea is that the "buy" day happens before the "sell" day, and we aim to find the best day to buy and the best day to sell based on the prices encountered so far.

Go Implementation

Solution Using One Pass Approach

go

package main

import "fmt"

// maxProfit returns the maximum profit that can be achieved from a list of prices
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    minPrice := prices[0] // Initialize the minimum price with the first day's price
    maxProfit := 0 // Initialize the maximum profit

    // Iterate through each price in the array
    for i := 1; i < len(prices); i++ {
        // Calculate the potential profit if we sold on day i
        profit := prices[i] - minPrice
        // Update the maximum profit if the current profit is higher
        if profit > maxProfit {
            maxProfit = profit
        }
        // Update the minimum price if the current price is lower
        if prices[i] < minPrice {
            minPrice = prices[i]
        }
    }

    return maxProfit
}

func main() {
    prices := []int{7, 1, 5, 3, 6, 4}
    result := maxProfit(prices)
    fmt.Println(result) // Output: 5
}

Explanation:

1. maxProfit Function:

• The function starts by initializing the minPrice to the price on the first day (prices[0]), and the maxProfit to 0 (indicating no profit at the beginning).
• We iterate through the prices starting from day 1. For each price:
• We calculate the potential profit by subtracting the minPrice from the current price.
• If this potential profit is greater than the current maxProfit, we update maxProfit.
• If the current price is lower than minPrice, we update minPrice to the current price.
• After iterating through all the prices, the function returns the maximum profit that can be achieved.

1. Main Function:

• In the main function, we define the prices array and call the maxProfit function to compute the result. Finally, we print the result.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Time Complexity:

• The time complexity is O(n), where n is the length of the prices array. We only traverse the array once, making it a one-pass solution.

Space Complexity:

• The space complexity is O(1) because we are using a constant amount of extra space (only a few variables to track the minimum price and maximum profit).

Edge Cases

1. Edge Case: No Prices

• Input: []
• Output: 0
• Explanation: If the prices array is empty, no transactions can be made, and the profit is 0.

1. Edge Case: All Prices Are the Same

• Input: [5, 5, 5, 5, 5]
• Output: 0
• Explanation: If all the prices are the same, no profit can be made, and the result should be 0.

1. Edge Case: Decreasing Prices

• Input: [7, 6, 4, 3, 1]
• Output: 0
• Explanation: If the prices are continuously decreasing, it is not possible to make a profit, so the result should be 0.

1. Edge Case: Single Price

• Input: [10]
• Output: 0
• Explanation: If there is only one price, no transaction can be made, so the profit is 0.

Conclusion

LeetCode 121: Best Time to Buy and Sell Stock is a classic problem that can be efficiently solved using a greedy algorithm. By keeping track of the minimum price encountered so far and calculating the potential profit at each step, we achieve an optimal solution with both time complexity of O(n) and space complexity of O(1).

This approach ensures that we can compute the maximum profit in linear time, even for large inputs.