Best Time - Transaction Fee

📋

Problem

Imagine you are a trader who can buy and sell stocks multiple times, but each sale costs a fixed transaction fee. How do you maximize your profit?

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 sale. You cannot hold more than one share of the stock at a time (i.e., you must sell the stock before you buy again). Return the maximum profit you can achieve.

1 ≤ prices.length ≤ 10^51 ≤ prices[i] ≤ 10^50 ≤ fee ≤ 10^5

Edge cases: prices with only one day → profit is 0fee = 0 → behaves like unlimited transactions without feeprices are strictly decreasing → profit is 0

</>

IDE

def maxProfit(prices: list[int], fee: int) -> int:public int maxProfit(int[] prices, int fee)int maxProfit(vector<int>& prices, int fee)function maxProfit(prices, fee)

def maxProfit(prices, fee):
    # Write your solution here
    pass

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxProfit(vector<int>& prices, int fee) {
    // Write your solution here
    return 0;
}

function maxProfit(prices, fee) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning zero profit due to missing state updates or fee handling.✅ Implement DP states for holding and not holding, update profits correctly with fee on sell.

Wrong: Incorrect positive profit when prices decreaseAllowing transactions even when unprofitable due to ignoring fee or price trends.✅ Only transact if profit after fee is positive; return 0 if no profitable transactions.

Wrong: Too low profit or missing multiple transactionsApplying fee on buy or missing multiple buy/sell pairs.✅ Subtract fee only on sell, allow multiple transactions by updating states each day.

Wrong: TLE or timeoutUsing exponential recursion or nested loops instead of O(n) DP.✅ Use bottom-up or memoized DP with O(n) time and O(1) space optimization.

Wrong: Profit less than optimal due to greedy early sellsGreedy approach selling too early without considering future prices.✅ Use DP state machine to hold stock longer and maximize profit after fees.

✓

Test Cases

Focus on handling edge cases like empty input and single day prices.

Test your solution against tricky cases that break greedy assumptions.

Ensure your solution is efficient enough for large inputs with O(n) complexity.

t1_01basic

Input{"prices":[1,3,2,8,4,9],"fee":2}

Expected8

⏱ Performance - must finish in 2000ms

Buy on day 0 (price=1), sell on day 3 (price=8), profit = 8 - 1 - 2 = 5. Then buy on day 4 (price=4), sell on day 5 (price=9), profit = 9 - 4 - 2 = 3. Total profit = 8.

💡 Think about tracking two states: holding a stock or not holding a stock.

💡 Use dynamic programming with states representing holding or not holding to decide buy/sell actions.

💡 Update dp states as dp_hold = max(dp_hold, dp_not_hold - price) and dp_not_hold = max(dp_not_hold, dp_hold + price - fee).

Why it failed: Incorrect profit likely due to missing transaction fee deduction on sell or incorrect state transitions. Fix by subtracting fee only when selling and correctly updating holding/not holding states.

✓ Correctly accounts for transaction fees and state transitions.

t1_02basic

Input{"prices":[1,5,3,6,4,8],"fee":1}

Expected8

⏱ Performance - must finish in 2000ms

Buy day 0 (1), sell day 1 (5), profit=5-1-1=3; buy day 2 (3), sell day 3 (6), profit=6-3-1=2; buy day 4 (4), sell day 5 (8), profit=8-4-1=3; total=8.

💡 Consider multiple buy/sell pairs with fee applied on each sell.

💡 Track max profit holding and not holding stock each day.

💡 Ensure fee is subtracted only on sell transactions, not on buy.

Why it failed: Profit too low or zero likely due to missing multiple transactions or fee applied incorrectly on buys. Fix by applying fee only on sells and allowing multiple transactions.

✓ Handles multiple profitable transactions with fees correctly.

t2_01edge

Input{"prices":[],"fee":5}

Expected0

⏱ Performance - must finish in 2000ms

Empty prices array means no transactions possible, profit is 0.

💡 Check how your code handles empty input arrays.

💡 Make sure base case returns 0 profit when no prices are given.

💡 Return 0 immediately if prices array is empty.

Why it failed: Code crashes or returns non-zero for empty prices. Fix by adding base case to return 0 if prices is empty.

✓ Correctly returns 0 profit for empty input.

t2_02edge

Input{"prices":[10],"fee":3}

Expected0

⏱ Performance - must finish in 2000ms

Only one day means no sell possible, so profit is 0.

💡 Consider that you cannot sell on the same day you buy.

💡 Profit requires at least two days to buy and sell.

💡 Return 0 if prices length is 1.

Why it failed: Returns non-zero profit for single day input. Fix by ensuring no profit if only one price is given.

✓ Correctly returns 0 profit for single day input.

t2_03edge

Input{"prices":[5,4,3,2,1],"fee":1}

Expected0

⏱ Performance - must finish in 2000ms

Prices strictly decreasing, no profitable transactions possible, profit is 0.

💡 Check if your code avoids buying when prices only go down.

💡 Profit should never be negative; ensure max with 0.

💡 Return 0 if no profitable transactions found.

Why it failed: Returns negative or positive profit when prices decrease. Fix by ensuring no transactions are made if unprofitable.

✓ Correctly returns 0 profit for strictly decreasing prices.

t3_01corner

Input{"prices":[1,3,7,5,10,3],"fee":3}

Expected6

⏱ Performance - must finish in 2000ms

Buy day 0 (1), sell day 2 (7), profit=7-1-3=3; buy day 3 (5), sell day 4 (10), profit=10-5-3=2; total=5. Actually best is buy day 0 sell day 4 profit=10-1-3=6.

💡 Beware of greedy approach that sells too early and misses bigger profits.

💡 Use DP to consider holding longer to maximize profit after fees.

💡 Update states to allow skipping sells to capture larger gains.

Why it failed: Greedy approach sells too early, missing larger profit. Fix by using DP state machine to consider holding longer before selling.

✓ Correctly avoids greedy trap and maximizes profit.

t3_02corner

Input{"prices":[1,3,2,8,4,9],"fee":0}

Expected13

⏱ Performance - must finish in 2000ms

With zero fee, profit is sum of all positive differences: (3-1)+(8-2)+(9-4)=2+6+5=13.

💡 Check if your code handles fee=0 correctly as unlimited transactions without fee.

💡 Profit should be sum of all positive price differences.

💡 Ensure fee subtraction is skipped when fee=0.

Why it failed: Incorrect profit when fee=0 due to always subtracting fee. Fix by conditionally subtracting fee only if fee > 0.

✓ Correctly handles zero fee as unlimited transactions.

t3_03corner

Input{"prices":[1,2,3,4,5],"fee":10}

Expected0

⏱ Performance - must finish in 2000ms

Fee larger than any price difference means no profitable transactions, profit is 0.

💡 Check if your code avoids transactions when fee exceeds all gains.

💡 Profit should be zero if fee is too large to allow profit.

💡 Return 0 if no profitable transactions after fee deduction.

Why it failed: Returns positive profit despite fee being too large. Fix by ensuring transactions only occur if profit after fee is positive.

✓ Correctly returns 0 profit when fee is too large.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) time solution to complete within 2 seconds.

💡 Brute force exponential solutions will time out on large inputs.

💡 Use O(n) dynamic programming with constant space optimization.

💡 Avoid recursion or nested loops to meet time constraints.

Why it failed: TLE due to exponential or quadratic complexity. Fix by implementing O(n) DP with state machine approach.

✓ Solution runs in O(n) time and passes performance test.

Practice

1. Consider the following Python code for climbing stairs:

def climb_stairs(n):
    if n <= 1:
        return 1
    first, second = 1, 1
    for _ in range(2, n + 1):
        current = first + second
        first, second = second, current
    return second

print(climb_stairs(4))

What is the value of the variable current during the last iteration of the loop?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace variable values for n=4

   Initialize first=1, second=1. Iterations: - i=2: current=1+1=2; first=1, second=2 - i=3: current=1+2=3; first=2, second=3 - i=4: current=2+3=5; first=3, second=5

2. Step 2: Identify last iteration's current value

   The last iteration is i=4, current=5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Last current computed is 5 for n=4 [OK]

Hint: Trace loop iterations carefully to find current value [OK]

Common Mistakes:

• Confusing loop bounds and off-by-one errors
• Returning previous current instead of last

2. Identify the bug in the following code snippet for calculating max profit from one stock transaction:

medium

A. Line 2: initializing min_price with prices[0] instead of infinity

B. Line 4: updating max_profit before updating min_price causes incorrect profit calculation

C. Line 5: the if condition should be prices[i] <= min_price

D. Line 6: returning max_profit instead of min_price

Solution

1. Step 1: Analyze update order in loop

   max_profit is updated before min_price, so profit may be calculated using outdated min_price.

2. Step 2: Identify correct update order

   min_price must be updated first to ensure profit calculation uses the lowest price so far.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping update order fixes incorrect profit calculation [OK]

Hint: Update min_price before max_profit in loop [OK]

Common Mistakes:

• Updating max_profit before min_price
• Using <= instead of < causing no difference
• Incorrect initialization rarely causes bugs here

3. Examine the following code snippet for climbing stairs:

def climb_stairs(n):
    if n < 1:
        return 1
    first, second = 1, 1
    for i in range(2, n + 1):
        current = first + second
        first, second = second, current
    return second

Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line 2: Incorrect base case condition should be 'if n <= 1'

B. Line 4: Loop range should start from 1 instead of 2

C. Line 5: The addition 'first + second' should be 'first - second'

D. Line 6: The tuple assignment order is reversed

Solution

1. Step 1: Analyze base case condition

   The condition 'if n < 1' returns 1 only when n is 0 or negative, but for n=1 it skips and runs the loop, which is incorrect.

2. Step 2: Correct base case to 'if n <= 1'

   This ensures for n=0 or n=1, the function returns 1 immediately, matching problem definition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Base case off-by-one causes wrong results for n=1 [OK]

Hint: Check base cases carefully for off-by-one errors [OK]

Common Mistakes:

• Using '<' instead of '<=' in base cases
• Incorrect loop start index

4. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why?

medium

A. O(n) because it iterates through the array once updating maxReach

B. O(n^2) because each position may check multiple jumps

C. O(n log n) due to sorting or priority queue operations

D. O(2^n) because of exploring all jump paths recursively

Solution

1. Step 1: Identify loop structure

   The greedy solution iterates through the array once, updating maxReach in O(1) time per iteration.

2. Step 2: Confirm no nested loops or recursion

   There are no nested loops or recursion, so total time is linear in array length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass over array -> O(n) time [OK]

Hint: Greedy uses single pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming sorting is needed
• Forgetting recursion stack space

5. Suppose the climbing stairs problem is modified so you can climb 1, 2, or 3 steps at a time. Which of the following changes to the space-optimized DP solution correctly computes the number of ways to reach the top?

hard

A. Keep two variables and update current as sum of the previous two only

B. Use three variables to store ways for last three steps and update current as their sum

C. Use recursion without memoization to handle the extra step size

D. Use a greedy approach to always take 3 steps when possible

Solution

1. Step 1: Understand the new step sizes

   With steps of size 1, 2, or 3, the number of ways to reach step i depends on the sum of ways to reach i-1, i-2, and i-3.

2. Step 2: Adjust space-optimized DP variables

   We need to track the last three computed values, so three variables are required to update current as their sum.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Summing last three states matches the new recurrence [OK]

Hint: Number of variables equals max step size for space optimization [OK]

Common Mistakes:

• Using only two variables for three-step jumps
• Recursion without memoization causes inefficiency