NUHMAN.com

Introduction

LeetCode 122: Best Time to Buy and Sell Stock II is an extension of the previous problem LeetCode 121 where you are allowed to perform multiple transactions. The goal is still to maximize your profit by buying and selling a stock, but this time, you can buy and sell the stock as many times as you want. The challenge is to find the maximum profit with multiple buy and sell operations, given an array prices[i] where each value represents the price of the stock on the ith day.

Problem Statement

You are given an array of integers prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing multiple days to buy and sell stocks. You may complete as many transactions as you like, but you must sell the stock before you buy again.

Return the maximum profit you can achieve from these transactions.

Example:

go

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

Approach:

Greedy Approach:

To maximize the profit when you can perform multiple transactions, you need to add up the profits from every consecutive increase in price. For example:

• If the price on day i is less than the price on day i+1, you should "buy" on day i and "sell" on day i+1, collecting the profit.
• Continue doing this throughout the array, summing the profits wherever the price increases.

Key Insight:

• We only care about the differences in prices where the price is increasing. Every time the price increases, we add that difference to our total profit.

Thus, the solution involves:

1. Iterating through the prices.
2. Whenever the price increases from one day to the next, we add the difference to our total profit.

This approach ensures that we capture all opportunities to profit from price increases, while ignoring the price decreases.

Go Implementation

Solution Using Greedy Approach

go

package main

import "fmt"

// maxProfit calculates the maximum profit that can be achieved
// by completing as many transactions as possible.
func maxProfit(prices []int) int {
    totalProfit := 0

    // Iterate through the prices
    for i := 1; i < len(prices); i++ {
        // If the price increases, buy at prices[i-1] and sell at prices[i]
        if prices[i] > prices[i-1] {
            totalProfit += prices[i] - prices[i-1]
        }
    }

    return totalProfit
}

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

Explanation:

1. maxProfit Function:

• The function initializes a variable totalProfit to 0, which will store the total profit.
• We iterate through the prices array starting from the second element.
• At each step, we check if the price on the current day is greater than the price on the previous day. If it is, we calculate the profit by subtracting the previous day's price from the current day's price and add it to totalProfit.
• This ensures that we are collecting profits whenever there's an increase in price.
• Finally, the function returns the totalProfit.

1. Main Function:

• The main function defines the prices array, calls the maxProfit function, and prints 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 need one pass through the array to calculate the total profit.

Space Complexity:

• The space complexity is O(1) because we are using a constant amount of extra space (just a variable to keep track of the total 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, so the result should be 0.

1. Edge Case: Prices Decrease Continuously

• Input: [7, 6, 4, 3, 1]
• Output: 0
• Explanation: If the prices are continuously decreasing, no transactions can be made to make a profit, so the result is 0.

1. Edge Case: Only One Price

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

Conclusion

LeetCode 122: Best Time to Buy and Sell Stock II is an extension of the problem where multiple transactions are allowed. By using a greedy approach, we can maximize the profit by adding the profit from each price increase in the array. This solution runs in O(n) time with O(1) space complexity, making it optimal for large inputs.

By focusing on the profitable opportunities where the price increases, we ensure an efficient solution that captures all potential profits.