Best Time to Buy and Sell Stock with Transaction Fee

MEDIUM

Description

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.

Note:

You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
The transaction fee is only charged once for each stock purchase and sale.

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:

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

Constraints:

1 <= prices.length <= 5 * 10⁴
1 <= prices[i] < 5 * 10⁴
0 <= fee < 5 * 10⁴

Approaches

Checkout 4 different approaches to solve Best Time to Buy and Sell Stock with Transaction Fee. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

This approach directly translates the problem into a recursive solution. For each day, we explore every possible action: if we hold a stock, we can either sell it or continue holding it; if we don't hold a stock, we can either buy one or rest. This generates a decision tree where every path represents a sequence of transactions, and we aim to find the path with the maximum profit.

Algorithm

Define a recursive function calculate(index, holding) that returns the maximum profit from day index onwards.
The holding parameter indicates if we currently possess a stock.
Base Case: If index goes beyond the array bounds, return 0 as no more profit can be made.
Recursive Step:
- If holding is true (we have a stock):
  - Option 1 (Sell): profit = prices[index] - fee + calculate(index + 1, false).
  - Option 2 (Hold): profit = calculate(index + 1, true).
  - Return the maximum of the two options.
- If holding is false (we don't have a stock):
  - Option 1 (Buy): profit = -prices[index] + calculate(index + 1, true).
  - Option 2 (Rest): profit = calculate(index + 1, false).
  - Return the maximum of the two options.
The initial call is calculate(0, false).

The brute-force method uses a recursive function to explore all possible sequences of buying and selling stocks. The function takes the current day's index and a boolean indicating whether a stock is currently held. From any given state, it recursively calls itself for the next day for all possible actions (buy/rest or sell/hold) and returns the maximum profit found among these choices. This exhaustive search guarantees finding the optimal solution but at a very high computational cost.

class Solution {
    public int maxProfit(int[] prices, int fee) {
        return calculate(prices, fee, 0, false);
    }

    private int calculate(int[] prices, int fee, int index, boolean holding) {
        if (index == prices.length) {
            return 0;
        }

        // Option to do nothing and move to the next day
        int doNothing = calculate(prices, fee, index + 1, holding);

        int doSomething;
        if (holding) {
            // Option to sell the stock
            doSomething = prices[index] - fee + calculate(prices, fee, index + 1, false);
        } else {
            // Option to buy the stock
            doSomething = -prices[index] + calculate(prices, fee, index + 1, true);
        }

        return Math.max(doNothing, doSomething);
    }
}

Complexity Analysis

Time Complexity: O(2^N), where N is the length of the `prices` array. For each day, the function branches into two possibilities, leading to an exponential number of calls.Space Complexity: O(N), where N is the number of days. This space is used by the recursion stack.

Pros and Cons

Pros:

Simple to conceptualize and implement.
Directly models the decision-making process at each step.

Cons:

Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.

Code Solutions

Checking out 3 solutions in different languages for Best Time to Buy and Sell Stock with Transaction Fee. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Best Time to Buy and Sell Stock with Transaction Fee

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

Citadel |