HomeLeetcode123. Best Time to Buy and Sell Stock III - Leetcode Solutions
Leetcode

123. Best Time to Buy and Sell Stock III – Leetcode Solutions

Declan Clarke

Description:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Examples:

Example 1:

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

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution in Python:

Python
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        # Initialize variables to store the maximum profit after each transaction
        first_buy = float('-inf')
        first_sell = 0
        second_buy = float('-inf')
        second_sell = 0

        for price in prices:
            # Update first buy - max profit if we buy stock at current price
            first_buy = max(first_buy, -price)
            # Update first sell - max profit if we sell stock at current price after first buy
            first_sell = max(first_sell, first_buy + price)
            # Update second buy - max profit if we buy stock at current price after first sell
            second_buy = max(second_buy, first_sell - price)
            # Update second sell - max profit if we sell stock at current price after second buy
            second_sell = max(second_sell, second_buy + price)

        # The second sell will have the maximum profit with at most two transactions
        return second_sell

Explanation

  1. Initial Checks:
    • If the prices list is empty, return 0 because no transactions can be made.
  2. Variable Initialization:
    • first_buy: The maximum profit achievable after the first buy. Initialized to negative infinity since we are “buying” stock.
    • first_sell: The maximum profit achievable after the first sell. Initialized to 0 because initially, we haven’t sold any stock.
    • second_buy: The maximum profit achievable after the second buy. Initialized to negative infinity for the same reason as first_buy.
    • second_sell: The maximum profit achievable after the second sell. Initialized to 0.
  3. Iterating through Prices:
    • For each price in the prices list:
      • Update first_buy to be the maximum of the current first_buy or the negative of the current price (-price). This simulates the action of buying the stock.
      • Update first_sell to be the maximum of the current first_sell or the sum of first_buy and the current price (first_buy + price). This simulates selling the stock after the first buy.
      • Update second_buy to be the maximum of the current second_buy or the difference between first_sell and the current price (first_sell - price). This simulates buying the stock again after the first sell.
      • Update second_sell to be the maximum of the current second_sell or the sum of second_buy and the current price (second_buy + price). This simulates selling the stock after the second buy.
  4. Returning the Result:
    • The value of second_sell will have the maximum profit achievable with at most two transactions.

Constraints

  • The function handles arrays with a length between 1 and 100,000.
  • Each price in the array is between 0 and 100,000.

This approach efficiently calculates the maximum profit in O(n) time complexity, where n is the length of the prices array.

Solution in Javascript:

JavaScript
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length === 0) {
        return 0;
    }

    // Initialize variables to store the maximum profit after each transaction
    let firstBuy = Number.NEGATIVE_INFINITY;
    let firstSell = 0;
    let secondBuy = Number.NEGATIVE_INFINITY;
    let secondSell = 0;

    // Iterate through the list of prices
    for (let price of prices) {
        // Update first buy - max profit if we buy stock at current price
        firstBuy = Math.max(firstBuy, -price);
        // Update first sell - max profit if we sell stock at current price after first buy
        firstSell = Math.max(firstSell, firstBuy + price);
        // Update second buy - max profit if we buy stock at current price after first sell
        secondBuy = Math.max(secondBuy, firstSell - price);
        // Update second sell - max profit if we sell stock at current price after second buy
        secondSell = Math.max(secondSell, secondBuy + price);
    }

    // The second sell will have the maximum profit with at most two transactions
    return secondSell;
};

Solution in Java:

Java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        // Initialize variables to store the maximum profit after each transaction
        int firstBuy = Integer.MIN_VALUE;
        int firstSell = 0;
        int secondBuy = Integer.MIN_VALUE;
        int secondSell = 0;

        // Iterate through the list of prices
        for (int price : prices) {
            // Update first buy - max profit if we buy stock at current price
            firstBuy = Math.max(firstBuy, -price);
            // Update first sell - max profit if we sell stock at current price after first buy
            firstSell = Math.max(firstSell, firstBuy + price);
            // Update second buy - max profit if we buy stock at current price after first sell
            secondBuy = Math.max(secondBuy, firstSell - price);
            // Update second sell - max profit if we sell stock at current price after second buy
            secondSell = Math.max(secondSell, secondBuy + price);
        }

        // The second sell will have the maximum profit with at most two transactions
        return secondSell;
    }
}

Solution in C#:

C#
public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) {
            return 0;
        }

        // Initialize variables to store the maximum profit after each transaction
        int firstBuy = int.MinValue;
        int firstSell = 0;
        int secondBuy = int.MinValue;
        int secondSell = 0;

        // Iterate through the list of prices
        foreach (int price in prices) {
            // Update first buy - max profit if we buy stock at current price
            firstBuy = Math.Max(firstBuy, -price);
            // Update first sell - max profit if we sell stock at current price after first buy
            firstSell = Math.Max(firstSell, firstBuy + price);
            // Update second buy - max profit if we buy stock at current price after first sell
            secondBuy = Math.Max(secondBuy, firstSell - price);
            // Update second sell - max profit if we sell stock at current price after second buy
            secondSell = Math.Max(secondSell, secondBuy + price);
        }

        // The second sell will have the maximum profit with at most two transactions
        return secondSell;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com