Jobs

Interviews

Discussions

Best Time to Buy and Sell Stock with Transaction Fee

Medium

TikTok

0 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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⁴

Best Time to Buy and Sell Stock with Transaction Fee

Medium

TikTok

0 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the price and fee values? Specifically, can they be negative, zero, or very large?
If no transaction is profitable (i.e., it's always better to do nothing), what should I return?
Is it possible to make multiple transactions on the same day (i.e., buy and sell on the same day)?
Is there a limit on the number of transactions I can make?
Can the input array `prices` be empty or null?

Brute Force Solution

Approach

The brute force method explores all possible combinations of buying and selling the stock. We'll go through every potential transaction and figure out the profit to find the best one. It's like checking every single path to see which one makes the most money, even if it takes a while.

Here's how the algorithm would work step-by-step:

Imagine you don't do anything at all. That's one possible outcome, and your profit is zero.
Now, consider buying the stock on the first day. Then, consider selling it on every day after that first day, calculating the profit (selling price minus buying price, minus the transaction fee) for each of those selling days.
Next, consider buying the stock on the second day. Again, consider selling it on every day after the second day, and calculate the profit for each scenario.
Keep doing this for every day as a potential buying day. For each buying day, try every possible selling day that comes later.
During this process, keep track of the highest profit you've found so far. Make sure to subtract the transaction fee each time you make a sale.
After you've explored every single possible combination of buying and selling, the highest profit you tracked is your answer.

Code Implementation

def max_profit_brute_force(prices, transaction_fee):
    max_total_profit = 0

    for buy_day in range(len(prices)):

        for sell_day in range(buy_day + 1, len(prices)):
            #We are considering all the days after the purchase to sell on
            potential_profit = prices[sell_day] - prices[buy_day] - transaction_fee

            if potential_profit > 0:
                #Track best profit possible
                max_total_profit = max(max_total_profit, potential_profit)

    # Return 0 if no transactions are made, otherwise return the max profit
    return max_total_profit

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach involves considering every possible buy and sell day pair. For each of the n possible buy days, we iterate through the remaining days to consider them as sell days. In the worst case, the first buy day will have n-1 possible sell days, the second buy day will have n-2 possible sell days, and so on. Summing this up leads to approximately n * (n-1) / 2 comparisons, which simplifies to O(n²).

Space Complexity

O(1) – The brute force approach, as described, only uses a few variables to keep track of the buying day, selling day, current profit, and maximum profit. No additional data structures, such as lists or maps, are created to store intermediate results. Therefore, the space required remains constant regardless of the number of days (N) in the input price list. The space complexity is O(1).

Optimal Solution

Approach

We want to find the most profit we can make by buying and selling stock, but each sale has a fee. The key idea is to track two things: how much money we have if we're holding stock and how much we have if we're not, updating these values as we go through the stock prices.

Here's how the algorithm would work step-by-step:

Imagine you start with no stock and zero money.
Go through each day's stock price one by one.
On each day, consider two possibilities: either you're holding stock or you're not.
If you're not holding stock, you can either keep not holding it, or you can buy it today. Choose the option that gives you more money.
If you are holding stock, you can either keep holding it, or sell it today. Remember to subtract the transaction fee when you sell. Choose the option that gives you more money.
Update your money values for holding and not holding stock based on the best choices you made that day.
Repeat this process for all days.
At the end, the amount of money you have when you're not holding stock is your maximum profit.

Code Implementation

def max_profit_with_transaction_fee(prices, fee):
    money_if_holding_stock = -float('inf')
    money_if_not_holding_stock = 0

    for price in prices:
        # Decide whether to buy stock if not holding it.

        previous_money_if_not_holding
        = money_if_not_holding_stock
        money_if_not_holding_stock = max(money_if_not_holding_stock,
                                          money_if_holding_stock + price - fee)

        # Decide whether to sell stock if holding it.

        money_if_holding_stock = max(money_if_holding_stock,
                                        previous_money_if_not_holding - price)

    # Max profit is when not holding stock at the end.

    return money_if_not_holding_stock

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of stock prices once. For each price, it performs a constant number of operations: updating the 'holding' and 'not holding' money values based on simple comparisons and arithmetic. Since the number of operations within the loop is constant and the loop runs n times, the overall time complexity is directly proportional to n.

Space Complexity

O(1) – The algorithm maintains two variables: one representing the money if holding stock and the other representing the money if not holding stock. These variables are updated in each iteration but their memory footprint remains constant regardless of the input size N (number of days/stock prices). Therefore, the auxiliary space used is constant, independent of the input size.

Edge Cases

Case	How to Handle
Empty price array	Return 0 profit immediately since no transactions are possible.
Single day (array with one element)	Return 0 profit because you cannot buy and sell on the same day.
Prices are monotonically increasing	Calculate profit by buying on the first day and selling on the last, subtracting the transaction fee for each transaction.
Prices are monotonically decreasing	Return 0 profit because no transaction will be profitable after considering the fee.
Transaction fee is zero	Solve as a regular buy and sell stock problem without a fee.
Transaction fee is larger than the price range	Return 0 profit since no transaction can be profitable.
Integer overflow with large prices and many transactions	Use a larger data type like long to store the profit to avoid overflow.
Prices array contains very large numbers	The DP solution should still function correctly as long as the intermediate calculations do not overflow; consider using larger datatypes if necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the price and fee values? Specifically, can they be negative, zero, or very large?
If no transaction is profitable (i.e., it's always better to do nothing), what should I return?
Is it possible to make multiple transactions on the same day (i.e., buy and sell on the same day)?
Is there a limit on the number of transactions I can make?
Can the input array `prices` be empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you don't do anything at all. That's one possible outcome, and your profit is zero.
Now, consider buying the stock on the first day. Then, consider selling it on every day after that first day, calculating the profit (selling price minus buying price, minus the transaction fee) for each of those selling days.
Next, consider buying the stock on the second day. Again, consider selling it on every day after the second day, and calculate the profit for each scenario.
Keep doing this for every day as a potential buying day. For each buying day, try every possible selling day that comes later.
During this process, keep track of the highest profit you've found so far. Make sure to subtract the transaction fee each time you make a sale.
After you've explored every single possible combination of buying and selling, the highest profit you tracked is your answer.

Code Implementation

def max_profit_brute_force(prices, transaction_fee):
    max_total_profit = 0

    for buy_day in range(len(prices)):

        for sell_day in range(buy_day + 1, len(prices)):
            #We are considering all the days after the purchase to sell on
            potential_profit = prices[sell_day] - prices[buy_day] - transaction_fee

            if potential_profit > 0:
                #Track best profit possible
                max_total_profit = max(max_total_profit, potential_profit)

    # Return 0 if no transactions are made, otherwise return the max profit
    return max_total_profit

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you start with no stock and zero money.
Go through each day's stock price one by one.
On each day, consider two possibilities: either you're holding stock or you're not.
If you're not holding stock, you can either keep not holding it, or you can buy it today. Choose the option that gives you more money.
If you are holding stock, you can either keep holding it, or sell it today. Remember to subtract the transaction fee when you sell. Choose the option that gives you more money.
Update your money values for holding and not holding stock based on the best choices you made that day.
Repeat this process for all days.
At the end, the amount of money you have when you're not holding stock is your maximum profit.

Code Implementation

def max_profit_with_transaction_fee(prices, fee):
    money_if_holding_stock = -float('inf')
    money_if_not_holding_stock = 0

    for price in prices:
        # Decide whether to buy stock if not holding it.

        previous_money_if_not_holding
        = money_if_not_holding_stock
        money_if_not_holding_stock = max(money_if_not_holding_stock,
                                          money_if_holding_stock + price - fee)

        # Decide whether to sell stock if holding it.

        money_if_holding_stock = max(money_if_holding_stock,
                                        previous_money_if_not_holding - price)

    # Max profit is when not holding stock at the end.

    return money_if_not_holding_stock

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty price array	Return 0 profit immediately since no transactions are possible.
Single day (array with one element)	Return 0 profit because you cannot buy and sell on the same day.
Prices are monotonically increasing	Calculate profit by buying on the first day and selling on the last, subtracting the transaction fee for each transaction.
Prices are monotonically decreasing	Return 0 profit because no transaction will be profitable after considering the fee.
Transaction fee is zero	Solve as a regular buy and sell stock problem without a fee.
Transaction fee is larger than the price range	Return 0 profit since no transaction can be profitable.
Integer overflow with large prices and many transactions	Use a larger data type like long to store the profit to avoid overflow.
Prices array contains very large numbers	The DP solution should still function correctly as long as the intermediate calculations do not overflow; consider using larger datatypes if necessary.