algoadvance

Leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day, and an integer fee representing a transaction fee.

Your goal is to maximize your profit by choosing a day to buy and a different day in the future to sell your stock. You can complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times), but you need to pay the transaction fee for each transaction.

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

Return the maximum profit you can achieve.

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved with the following transactions:
- Buy on day 1 (price = 1) and sell on day 4 (price = 8), profit = 8 - 1 - 2 = 5
- Buy on day 5 (price = 4) and sell on day 6 (price = 9), profit = 9 - 4 - 2 = 3
Total profit = 5 + 3 = 8.

Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Constraints:

• 1 <= prices.length <= 5 * 10^4
• 0 <= prices[i], fee < 5 * 10^4

Clarifying Questions

1. Can the transaction fee vary for different buys and sells?
   • No, the transaction fee is constant for all transactions.
2. Can the fee be larger than the prices of the stock?
   • Yes, the fee can be larger than some or all of the stock prices.
3. Is it guaranteed to get at least one profitable transaction?
   • No, the output can be zero if no profitable transactions can be made due to high fees or unsuitable price movements.

Strategy

We’ll use a dynamic programming approach to solve this problem. We’ll maintain two states, cash and hold:

• cash - The maximum profit we can have if we do not hold any stock at the current day.
• hold - The maximum profit we can have if we hold one share of stock at the current day.

The goal is to traverse through each day and update these states.

1. On day i, if we do not hold any stock, the maximum profit is either we did not hold a stock on day i-1 as well, or we sold the stock on day i (taking fee into account).
2. Similarly, if we hold a stock on day i, it means either we held the stock on day i-1 as well, or we bought the stock on day i deducting the price.

We’ll initialize cash as 0 (since no stock holding implies 0 profit initially) and hold as negative infinity (since we haven’t bought any stock yet).

The state transitions will be:

• cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee)
• hold[i] = max(hold[i-1], cash[i-1] - prices[i])

Finally, the result will be stored in cash since selling stock would be more beneficial or equal to holding on the last day.

Code

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;

        // Initial conditions
        int cash = 0;
        int hold = -prices[0];

        // Traverse through prices to update states
        for (int i = 1; i < n; i++) {
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, cash - prices[i]);
        }

        // Return the maximum profit without stock holding
        return cash;
    }
}

Time Complexity

• Time Complexity: O(n) where n is the length of the prices array.
  • We only need to traverse the array once.
• Space Complexity: O(1)
  • We’re using a constant amount of extra space for variables cash and hold.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?