Best Time to Buy and Sell Stock with Transaction Fee

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

Understanding the Visualization

Input

Array of stock prices over time and transaction fee

Process

Find optimal buy-sell sequence considering fees

Output

Maximum profit achievable after paying all fees

Key Takeaway

🎯 Key Insight: Track two states (holding vs cash) and ensure each transaction profit exceeds the fee

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

Approach	Time	Space	Notes
✓ Dynamic Programming - Bottom Up	O(n)	O(1)	Track maximum profit in two states: holding stock vs having cash
Greedy - Buy Low, Sell High	O(n)	O(1)	Use greedy approach to identify profitable buy-sell opportunities
Brute Force - Try All Combinations	O(3ⁿ)	O(n)	Try every possible sequence of buy and sell operations
Memoization - Cache Recursive Results	O(n)	O(n)	Optimize brute force by caching results for (day, holding) states

Dynamic Programming - Bottom Up — Algorithm Steps

Step 1: Initialize two states - hold (have stock) and cash (no stock)
Step 2: For each day, calculate new hold and cash values
Step 3: hold = max(previous hold, previous cash - price)
Step 4: cash = max(previous cash, previous hold + price - fee)
Step 5: Return final cash value (we want to end without holding stock)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize States

hold = -prices[0], cash = 0

Update States

For each price, calculate new hold and cash

Final Answer

Return cash (profit without holding stock)

Code -

solution.c — C

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

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* prices, int pricesSize, int fee) {
    if (pricesSize == 0) {
        return 0;
    }
    
    // hold: maximum profit when holding a stock
    // cash: maximum profit when not holding a stock
    int hold = -prices[0];  // Buy first stock
    int cash = 0;           // Don't buy anything
    
    for (int i = 1; i < pricesSize; i++) {
        int newHold = max(hold, cash - prices[i]);  // Keep holding or buy today
        int newCash = max(cash, hold + prices[i] - fee);  // Keep cash or sell today
        
        hold = newHold;
        cash = newCash;
    }
    
    return cash;  // We want to end without holding stock
}

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(n)

Single pass through array, constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only store two variables for current states

✓ Linear 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Bottom Up — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler