What is the time complexity of Best Time to Buy and Sell Stock with Transaction Fee?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Best Time to Buy and Sell Stock with Transaction Fee?

This problem uses Array, Dynamic Programming, Greedy. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Best Time to Buy and Sell Stock with Transaction Fee?

Insight 1: The problem can be solved using dynamic programming, where we keep track of two states: `cash` (maximum profit when not holding a stock) and `hold` (maximum profit when holding a stock). Insight 2: Each day, we can either continue holding the stock or sell it (if holding). Similarly, we can either continue not holding or buy the stock (if not holding).

Which companies ask LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee in interviews?

This problem is frequently asked at Citadel.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Best Time to Buy and Sell Stock with Transaction Fee - LeetCode 714 Solution

Best Time to Buy and Sell Stock with Transaction Fee - Complete Solution Guide

Best Time to Buy and Sell Stock with Transaction Fee is LeetCode problem 714, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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. Example

Detailed Explanation

The problem asks us to find the maximum profit that can be obtained by buying and selling stocks with a transaction fee. We are given an array `prices` representing the stock prices on each day and an integer `fee` representing the transaction fee for each buy and sell operation. We can perform multiple transactions, but we can't hold multiple stocks simultaneously (i.e., we must sell before buying again). The goal is to maximize the total profit after accounting for the transaction fees.

Solution Approach

The solution uses a dynamic programming approach with two variables, `cash` and `hold`. `cash` represents the maximum profit if we don't hold any stock at the end of the day, and `hold` represents the maximum profit if we hold a stock at the end of the day. We iterate through the `prices` array, updating `cash` and `hold` at each step. At each day, we consider two options for each state: either keep the state from the previous day or transition to the other state by buying or selling.

Step-by-Step Algorithm

Step 1: Initialize `cash` to 0 (no profit initially) and `hold` to `-prices[0]` (the profit/loss if we buy on the first day).
Step 2: Iterate through the `prices` array from the second day (index 1).
Step 3: For each day `i`, calculate the new `cash` value. This is the maximum of the previous `cash` value (no action) and the `hold` value plus the current price minus the fee (selling the stock). Crucially, we store the *previous* cash value before we update it.
Step 4: For each day `i`, calculate the new `hold` value. This is the maximum of the previous `hold` value (no action) and the previous `cash` value minus the current price (buying the stock). We use the *previous* cash value because the current cash value reflects whether we sold *today*, but our hold state represents whether we would buy today.
Step 5: Update `cash` and `hold` variables with the calculated values.
Step 6: After iterating through all the prices, the maximum profit will be stored in `cash` because at the end, we prefer not holding the stock.

Key Insights

Insight 1: The problem can be solved using dynamic programming, where we keep track of two states: `cash` (maximum profit when not holding a stock) and `hold` (maximum profit when holding a stock).
Insight 2: Each day, we can either continue holding the stock or sell it (if holding). Similarly, we can either continue not holding or buy the stock (if not holding).
Insight 3: The transaction fee is only applied when selling the stock, so it affects the `cash` state when transitioning from `hold` to `cash`.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming, Greedy.

Companies

Asked at: Citadel.

Best Time to Buy and Sell Stock with Transaction Fee | LeetCode 714

Medium

Array Dynamic Programming Greedy

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

Solution Code

Available in:

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0;
        int hold = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];

            // Store the previous day's cash profit to use in the hold calculation.
            // This is necessary because we update `cash` before `hold`.
            int prev_cash = cash;

            // Update cash: maximum of (not holding, so same as yesterday's cash) 
            // or (selling today, from yesterday's hold state).
            cash = Math.max(cash, hold + price - fee);

            // Update hold: maximum of (holding, so same as yesterday's hold)
            // or (buying today, from yesterday's cash state).
            hold = Math.max(hold, prev_cash - price);
        }

        return cash;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 714: Best Time to Buy and Sell Stock with Transaction Fee - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Greedy

Companies

Citadel

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:714

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize `cash` to 0 (no profit initially) and `hold` to `-prices[0]` (the profit/loss if we buy on the first day).
2
Step 2: Iterate through the `prices` array from the second day (index 1).
3
Step 3: For each day `i`, calculate the new `cash` value. This is the maximum of the previous `cash` value (no action) and the `hold` value plus the current price minus the fee (selling the stock). Crucially, we store the *previous* cash value before we update it.
4
Step 4: For each day `i`, calculate the new `hold` value. This is the maximum of the previous `hold` value (no action) and the previous `cash` value minus the current price (buying the stock). We use the *previous* cash value because the current cash value reflects whether we sold *today*, but our hold state represents whether we would buy today.
5
Step 5: Update `cash` and `hold` variables with the calculated values.
6
Step 6: After iterating through all the prices, the maximum profit will be stored in `cash` because at the end, we prefer not holding the stock.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because the algorithm iterates through the prices array once. The space complexity is constant because only a fixed number of variables are used.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dynamic Programming with Array

Use two arrays, `cash` and `hold`, of size n, to store the maximum profit at each day for both states (holding and not holding).

Time: O(n)Space: O(n)

Trade-offs: This approach is less space-efficient than the O(1) space solution, but it can be more intuitive for some beginners. The O(1) space solution is an optimized version of this approach.

✨

Key Insights

1Insight 1: The problem can be solved using dynamic programming, where we keep track of two states: `cash` (maximum profit when not holding a stock) and `hold` (maximum profit when holding a stock).
2Insight 2: Each day, we can either continue holding the stock or sell it (if holding). Similarly, we can either continue not holding or buy the stock (if not holding).
3Insight 3: The transaction fee is only applied when selling the stock, so it affects the `cash` state when transitioning from `hold` to `cash`.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Edge Cases

Edge case 1: Empty `prices` array. The C solution handles this case explicitly returning 0, others work correctly with empty input due to loop condition.
Edge case 2: Only one price in the array. In this case, no profit can be made, and the `cash` variable remains 0, which is the correct answer.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not accounting for the transaction fee when calculating the profit from selling a stock.

✗Common mistake 2: Incorrectly updating `cash` and `hold` values by not using the previous day's values when buying. This can lead to incorrect results.

✗Common mistake 3: Trying to solve this problem with brute force, which would lead to exponential time complexity and exceed time limits for larger inputs.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Algorithmic trading, where maximizing profit with transaction costs (fees, commissions) is crucial.

🏦Real-world scenario 2: Financial planning, where you want to determine the optimal buy/sell strategy for assets while considering transaction fees.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Best Time to Buy and Sell Stock with Transaction Fee"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?