Best Time to Buy and Sell Stock with Transaction Fee - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: prices = [1, 3, 2, 8, 4, 9], fee = 2

› Output: 8

💡 Note: Maximum profit is 8: buy at price 1, sell at price 8 (profit = 8-1-2 = 5), then buy at price 4, sell at price 9 (profit = 9-4-2 = 3). Total profit = 5 + 3 = 8.

Example 2 — High Transaction Fee

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

› Output: 6

💡 Note: Best strategy: buy at 1, sell at 10 (profit = 10-1-3 = 6). Other transactions would be less profitable due to high fee.

Example 3 — No Profitable Transactions

$ Input: prices = [5, 4, 3, 2, 1], fee = 1

› Output: 0

💡 Note: Prices are decreasing, so no profitable transactions are possible. Any buy-sell combination would result in loss.

Constraints

1 ≤ prices.length ≤ 5 × 10⁴
1 ≤ prices[i] < 5 × 10⁴
0 ≤ fee < 5 × 10⁴

Visualization

Tap to expand

Asked in

f Facebook 15 G Google 12 a Amazon 18 M Microsoft 10

The key insight is to track two states: maximum profit when holding stock vs when having cash. The dynamic programming approach is optimal with state transitions: hold = max(prev_hold, prev_cash - price) and cash = max(prev_cash, prev_hold + price - fee). Time: O(n), Space: O(1)

Common Approaches

✓ Brute Force - Try All Combinations

⏱️ Time: O(3ⁿ) Space: O(n)

For each day, recursively try buying (if not holding), selling (if holding), or doing nothing. Calculate profit for each valid sequence and return maximum.

Dynamic Programming - Bottom Up

⏱️ Time: O(n) Space: O(1)

Use dynamic programming to track two states at each day: maximum profit when holding a stock and maximum profit when not holding a stock. Build solution iteratively from first day to last.

Greedy - Buy Low, Sell High

⏱️ Time: O(n) Space: O(1)

Look for profitable transactions by tracking potential buy price and selling when profit exceeds the transaction fee. Reset buy price after each profitable sale.

Memoization - Cache Recursive Results

⏱️ Time: O(n) Space: O(n)

Same recursive approach as brute force but cache results for each (day, holding_stock) combination to avoid recomputing the same subproblems.

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Use recursion to try all possible buy/sell sequences
Step 2: For each day, try buying, selling, or holding
Step 3: Calculate total profit minus transaction fees
Step 4: Return maximum profit across all valid sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursion Tree

Each day branches into buy/sell/hold decisions

State Tracking

Track current day and whether holding stock

Maximum Profit

Return best profit across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dfs(int* prices, int pricesSize, int fee, int day, int holding) {
    if (day >= pricesSize) {
        return 0;
    }
    
    // Option 1: Do nothing
    int result = dfs(prices, pricesSize, fee, day + 1, holding);
    
    if (holding) {
        // Option 2: Sell
        int sellProfit = prices[day] - fee + dfs(prices, pricesSize, fee, day + 1, 0);
        if (sellProfit > result) result = sellProfit;
    } else {
        // Option 2: Buy
        int buyProfit = -prices[day] + dfs(prices, pricesSize, fee, day + 1, 1);
        if (buyProfit > result) result = buyProfit;
    }
    
    return result;
}

int solution(int* prices, int pricesSize, int fee) {
    return dfs(prices, pricesSize, fee, 0, 0);
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int prices[1000];
    int pricesSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[pricesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int fee;
    scanf("%d", &fee);
    
    int result = solution(prices, pricesSize, fee);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

Each day has 3 choices (buy/sell/hold), creating exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals array length

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

4.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Best Time to Buy and Sell Stock with Transaction Fee - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler