Maximize profit with transaction fees
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an array prices where prices[i] is the price of a stock on day i and an integer fee representing the commission charged when you sell. You may complete as many transactions as you like (buy one and later sell one share), but you must sell before you buy again and can hold at most one share at a time. Return the maximum net profit achievable. Describe your algorithm and analyze time and space complexity. Follow-ups: How would the solution change if the fee were charged on both buy and sell, or if multiple shares could be held concurrently?
Quick Answer: This question evaluates algorithm design skills, specifically understanding of dynamic programming and greedy strategies for optimizing profit under transaction fees, along with stateful decision-making and handling cost constraints.
You are given an integer array `prices` where `prices[i]` is the price of a given stock on day `i`, and an integer `fee` representing a commission charged each time you sell.
You may complete as many transactions as you like (buy one share and later sell one share of the stock), but you must sell the share before you buy again, and you can hold at most one share at any time. The fee is charged on each completed sale.
Return the **maximum net profit** you can achieve.
Example:
- `prices = [1, 3, 2, 8, 4, 9]`, `fee = 2` -> `8`. Buy at 1, sell at 8 (profit 8-1-2 = 5), buy at 4, sell at 9 (profit 9-4-2 = 3). Total = 8.
Follow-ups to discuss (not graded): How would the solution change if the fee were charged on both buy and sell? What if you could hold multiple shares concurrently?
Constraints
- 1 <= prices.length <= 5 * 10^4
- 1 <= prices[i] < 5 * 10^4
- 0 <= fee < 5 * 10^4
- An empty prices array returns 0.
Examples
Input: ([1, 3, 2, 8, 4, 9], 2)
Expected Output: 8
Explanation: Buy at 1, sell at 8 (5-2... net 5), buy at 4, sell at 9 (net 3): 5+3 = 8.
Input: ([1, 3, 7, 5, 10, 3], 3)
Expected Output: 6
Explanation: Buy at 1, sell at 10 (10-1-3 = 6). A single transaction beats splitting because each sale costs the fee.
Hints
- Track two running states as you scan the days: the best net profit while holding no share (cash) and the best net profit while holding one share (hold).
- On each day, you can sell (cash = max(cash, hold + price - fee)) or buy (hold = max(hold, cash - price)). Subtract the fee once per completed sale.
- Initialize cash = 0 and hold = -prices[0], then iterate from day 1. The answer is cash at the end, since ending while holding a share is never better than having sold.