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.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Clarifying Questions

Before we proceed to solve the problem, let’s clarify the following:

1. Can prices array be empty? (Assume it can’t since there wouldn’t be any possible transaction.)
2. Is the transaction fee always non-negative?
3. Are there any constraints on the size of the prices array?

Assumed Constraints:

• The array prices will have at least one price entry.
• The transaction fee will be a non-negative integer.
• The size of the prices array would typically be up to the order of 10^5.

Strategy

We’ll use dynamic programming to solve this problem. We’ll define two states:

• cash: The maximum profit we can have if we are not holding any stock.
• hold: The maximum profit we can have if we are holding one stock.

State Transitions:

• If we have no stock today (cash), we can either:
  1. Do nothing (stay in the cash state),
  2. Sell the stock we have been holding (transition from the hold state to the cash state).

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

• If we have stock today (hold), we can either:
  1. Do nothing (stay in the hold state),
  2. Buy new stock (transition from the cash state to the hold state).

  hold = max(hold, cash - prices[i])

We initialize:

• cash to 0, because initially we have no stock and no profit.
• hold to -prices[0] since buying the first stock costs us the price on the first day.

Finally, after processing all days, the maximum profit will be in the cash state.

Time Complexity

The time complexity of this approach is (O(n)) where (n) is the number of days (the length of the prices array). This is because we are iterating through the prices array once.

Code

Here is the C++ code that implements the above strategy:

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProfit(std::vector<int>& prices, int fee) {
        int n = prices.size();
        if (n == 0) return 0;

        // Initialize the variables to represent the two states.
        int cash = 0;
        int hold = -prices[0];

        // Traverse each price in the prices array.
        for (int i = 1; i < n; ++i) {
            // Update cash (no stock in hand) and hold (stock in hand) states.
            cash = std::max(cash, hold + prices[i] - fee);
            hold = std::max(hold, cash - prices[i]);
        }

        // The maximum profit will be in the cash state at the end of the array.
        return cash;
    }
};

Explanation of the Code

1. Initialization of cash and hold.
2. Loop through each day and update cash and hold using the derived formulas.
3. Return cash after processing all the prices which holds the maximum profit we can get without holding any stock.

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?