Best Time - Transaction Fee

▶

Steps

setup

Initialize cash and hold for day 0

Set cash to 0 since no stock is held initially, and hold to -prices[0] because buying stock on day 0 costs price 1.

💡 Initialization sets the base case: no profit without stock, and holding stock means negative profit equal to the purchase price.

Line:

cash, hold = 0, -prices[0]

💡 The algorithm starts with two states representing the initial conditions of holding or not holding stock.

fill_cells

Process day 1 price = 3: update cash

Calculate cash for day 1 as max of previous cash (0) or selling stock today (hold + price - fee = -1 + 3 - 2 = 0).

💡 This step decides if selling today yields better profit than doing nothing.

Line:

cash = max(cash, hold + price - fee)

💡 Selling today does not increase profit compared to doing nothing, so cash remains 0.

fill_cells

Process day 1 price = 3: update hold

Calculate hold for day 1 as max of previous hold (-1) or buying today (cash - price = 0 - 3 = -3).

💡 This step decides if buying today is better than holding from before.

Line:

hold = max(hold, cash - price)

💡 Holding from day 0 is better than buying today at price 3.

fill_cells

Process day 2 price = 2: update cash

Calculate cash for day 2 as max of previous cash (0) or selling stock today (hold + price - fee = -1 + 2 - 2 = -1).

💡 Check if selling today improves profit over doing nothing.

Line:

cash = max(cash, hold + price - fee)

💡 Selling today is not profitable; keep previous cash.

fill_cells

Process day 2 price = 2: update hold

Calculate hold for day 2 as max of previous hold (-1) or buying today (cash - price = 0 - 2 = -2).

💡 Decide if buying today is better than holding from before.

Line:

hold = max(hold, cash - price)

💡 Holding from day 0 remains the best option.

fill_cells

Process day 3 price = 8: update cash

Calculate cash for day 3 as max of previous cash (0) or selling stock today (hold + price - fee = -1 + 8 - 2 = 5).

💡 Selling today yields a profit of 5, better than previous cash.

Line:

cash = max(cash, hold + price - fee)

💡 Selling at price 8 after buying at 1 minus fee yields profit 5.

fill_cells

Process day 3 price = 8: update hold

Calculate hold for day 3 as max of previous hold (-1) or buying today (cash - price = 5 - 8 = -3).

💡 Decide if buying today is better than holding from before.

Line:

hold = max(hold, cash - price)

💡 Holding from before is better than buying today at 8.

fill_cells

Process day 4 price = 4: update cash

Calculate cash for day 4 as max of previous cash (5) or selling stock today (hold + price - fee = -1 + 4 - 2 = 1).

💡 Check if selling today improves profit over previous cash.

Line:

cash = max(cash, hold + price - fee)

💡 Selling today is less profitable than previous cash.

fill_cells

Process day 4 price = 4: update hold

Calculate hold for day 4 as max of previous hold (-1) or buying today (cash - price = 5 - 4 = 1).

💡 Decide if buying today is better than holding from before.

Line:

hold = max(hold, cash - price)

💡 Buying today at price 4 after profit 5 is better than previous hold.

fill_cells

Process day 5 price = 9: update cash

Calculate cash for day 5 as max of previous cash (5) or selling stock today (hold + price - fee = 1 + 9 - 2 = 8).

💡 Selling today yields profit 8, better than previous cash 5.

Line:

cash = max(cash, hold + price - fee)

💡 Selling at price 9 after buying at 4 minus fee yields profit 8 total.

fill_cells

Process day 5 price = 9: update hold

Calculate hold for day 5 as max of previous hold (1) or buying today (cash - price = 8 - 9 = -1).

💡 Decide if buying today is better than holding from before.

Line:

hold = max(hold, cash - price)

💡 Holding from day 4 is better than buying today at 9.

reconstruct

Return final max profit

Return cash at last day (day 5) which is 8, the maximum profit achievable.

💡 The cash state at the last day represents max profit without holding stock.

Line:

return cash

💡 The answer is the maximum profit after all transactions and fees.

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]  # STEP 1: initialize
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)  # STEP 2,4,6,8,10: update cash
        hold = max(hold, cash - price)        # STEP 3,5,7,9,11: update hold
    return cash  # STEP 12: return result

if __name__ == '__main__':
    prices = [1,3,2,8,4,9]
    fee = 2
    print(maxProfit(prices, fee))  # Output: 8

📊

Best Time - Transaction Fee - Watch the Algorithm Execute, Step by Step

Watching each update of cash and hold variables reveals the decision-making process behind maximizing profit with transaction fees, making the dynamic programming approach intuitive.

Item 0 - wt:1 val:1

i\w	0	1	2	3	4	5
i=0	-1	?	?	?	?	?
i=1	0	?	?	?	?	?

hold = -1

Item 1 - wt:3 val:3

i\w	0	1	2	3	4	5
i=0	-1	?	?	?	?	?
i=1	0	0	?	?	?	?

cash = max(0, 0) = 0

Item 1 - wt:3 val:3

i\w	0	1	2	3	4	5
i=0	-1	-1	?	?	?	?
i=1	0	0	?	?	?	?

hold = max(-1, -3) = -1

Item 2 - wt:2 val:2

i\w	0	1	2	3	4	5
i=0	-1	-1	?	?	?	?
i=1	0	0	0	?	?	?

cash = max(0, -1) = 0

Item 2 - wt:2 val:2

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	?	?	?
i=1	0	0	0	?	?	?

hold = max(-1, -2) = -1

Item 3 - wt:8 val:8

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	?	?	?
i=1	0	0	0	5	?	?

cash = max(0, 5) = 5

Item 3 - wt:8 val:8

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	-1	?	?
i=1	0	0	0	5	?	?

hold = max(-1, -3) = -1

Item 4 - wt:4 val:4

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	-1	?	?
i=1	0	0	0	5	5	?

cash = max(5, 1) = 5

Item 4 - wt:4 val:4

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	-1	1	?
i=1	0	0	0	5	5	?

hold = max(-1, 1) = 1

Item 5 - wt:9 val:9

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	-1	1	?
i=1	0	0	0	5	5	8

cash = max(5, 8) = 8

Item 5 - wt:9 val:9

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	-1	1	1
i=1	0	0	0	5	5	8

hold = max(1, -1) = 1

Item 5 - wt:9 val:9

i\w	0	1	2	3	4	5
i=0	-1	-1	-1	-1	1	1
i=1	0	0	0	5	5	8

answer = 8

Key Takeaways

✓ The algorithm models the problem with two states: holding stock and not holding stock, updating them day by day.

This insight is hard to see from code alone because the variables 'cash' and 'hold' abstract away the state machine logic.

✓ Each day's cash and hold values depend only on the previous day's states, showing a clear dynamic programming dependency.

Visualizing these dependencies clarifies why the algorithm is efficient and how it avoids recomputation.

✓ Decisions to buy or sell are made by comparing current and potential profits, reflected in max operations updating cash and hold.

Seeing these decisions step-by-step helps understand when it is optimal to buy, sell, or hold.

Practice

1. You are given a circular street with houses arranged in a loop, each containing some amount of money. You want to maximize the amount you rob without robbing two adjacent houses, and since the street is circular, the first and last houses are also adjacent. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that always picks the house with the maximum money first

B. Dynamic programming by splitting the problem into two linear subproblems excluding either the first or last house

C. Brute force recursion checking all subsets of houses

D. Sorting houses by money and robbing every other house

Solution

1. Step 1: Understand circular adjacency constraint

   The first and last houses cannot both be robbed, so the problem is not a simple linear DP.

2. Step 2: Split into two linear problems

   By considering two cases--rob houses from first to second last, or from second to last--we reduce the circular problem to two linear House Robber problems solvable by DP.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Splitting into two linear DP subproblems handles circular adjacency correctly [OK]

Hint: Split circular problem into two linear DP cases [OK]

Common Mistakes:

• Assuming greedy or sorting works
• Trying to rob first and last house together
• Using brute force without pruning

2. Consider the following code snippet implementing the optimal Jump Game solution. What is the value of maxReach after the third iteration (i=2) when input is [2,0,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace iterations for input [2,0,2]

   i=0: maxReach = max(0, 0+2) = 2; i=1: maxReach = max(2, 1+0) = 2; i=2: maxReach = max(2, 2+2) = 4

2. Step 2: Identify maxReach after third iteration (i=2)

   After i=2, maxReach is 4, which is the value after the third iteration completes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   maxReach updated to 4 after i=2 [OK]

Hint: Track maxReach updates carefully at each iteration [OK]

Common Mistakes:

• Off-by-one error in iteration count
• Confusing maxReach before vs after update
• Ignoring early return conditions

3. What is the time complexity of the optimal bottom-up dynamic programming solution for the minimum cost climbing stairs problem, and why?

medium

A. O(n) because each step computes cost using only two previous states

B. O(n²) because each step depends on all previous steps

C. O(2^n) due to exponential recursion calls

D. O(n log n) because of sorting costs before processing

Solution

1. Step 1: Analyze loop structure

   The bottom-up DP iterates once through the cost array of length n.

2. Step 2: Check dependencies per iteration

   Each iteration computes current cost using only two previous values, constant time per iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) work per step -> O(n) total [OK]

Hint: DP uses constant work per step, linear total time [OK]

Common Mistakes:

• Assuming quadratic due to nested loops
• Confusing recursion with DP iteration
• Thinking sorting is involved

4. Suppose the problem is modified so that you can reuse the same stock multiple times within a single transaction (i.e., buy and sell multiple times without waiting). Which modification to the DP approach correctly handles this variant?

hard

A. Modify the DP to allow buying again without decrementing transactions_left when holding a stock

B. Increase k to a very large number and use the unlimited transactions solution shortcut

C. Use the same DP but skip updating buy states to avoid multiple buys

D. Use a greedy approach to sum all positive price differences without DP

Solution

1. Step 1: Understand the reuse variant

   Reusing stock within a transaction means multiple buys/sells without reducing transaction count on buys.

2. Step 2: Modify DP state transitions

   Allow buy state updates without decrementing transactions_left, so holding state can be refreshed multiple times per transaction.

3. Step 3: Why other options fail

   Unlimited transactions shortcut ignores transaction limit; skipping buy updates breaks profit calculation; greedy fails with transaction constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct DP modification respects transaction count and allows multiple buys per transaction [OK]

Hint: Allow buy updates without reducing transactions_left [OK]

Common Mistakes:

• Using unlimited transactions shortcut incorrectly
• Skipping buy updates breaks DP correctness

5. Suppose the stock trading problem is modified so that you must pay a transaction fee for each sale. Which of the following changes to the state machine DP solution correctly accounts for the fee while maintaining optimal profit calculation?

hard

A. Add the fee to both buying and selling updates to ensure fee is counted twice

B. Subtract the fee from the buying price when updating holding: holding = max(holding, prev_not_holding - prices[i] - fee)

C. Subtract the fee from the selling price when updating not_holding: not_holding = max(not_holding, holding + prices[i] - fee)

D. Ignore the fee in DP and subtract total fee at the end from final profit

Solution

1. Step 1: Understand fee impact

   The fee applies on each sale, so it should reduce the profit gained when selling.

2. Step 2: Adjust DP transitions

   Subtract fee from the selling transition: not_holding = max(not_holding, holding + prices[i] - fee). Buying price remains unchanged.

3. Step 3: Why other options fail

   Subtracting fee on buying overcharges; adding fee twice double counts; ignoring fee until end breaks DP correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Fee reduces profit only on selling, correctly modeled in not_holding update [OK]

Hint: Fee applies only on selling, subtract from selling transition [OK]

Common Mistakes:

• Subtracting fee on buying instead of selling
• Double counting fee on buy and sell
• Ignoring fee in DP transitions