What is the time complexity of Best Time to Buy and Sell Stock III?

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

What data structures are used to solve Best Time to Buy and Sell Stock III?

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

What are the key insights for solving Best Time to Buy and Sell Stock III?

Insight 1: We can think of the problem as finding the best split point in the `prices` array and maximizing profit from the left and right subarrays independently. However, iterating through all split points would be O(n^2). Insight 2: The optimal solution avoids explicitly splitting the array. Instead, it uses dynamic programming with constant space to track the maximum profit after at most two transactions by maintaining four variables: buy1, sell1, buy2, and sell2, representing buying the first stock, selling the first stock, buying the second stock, and selling the second stock respectively.

Which companies ask LeetCode 123. Best Time to Buy and Sell Stock III in interviews?

This problem is frequently asked at Bolt, Citadel, Groww, PhonePe, Snap and 4 more companies.

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

Best Time to Buy and Sell Stock III - LeetCode 123 Solution

Best Time to Buy and Sell Stock III - Complete Solution Guide

Best Time to Buy and Sell Stock III is LeetCode problem 123, a Hard 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. Find the maximum profit you can achieve. You may complete at most two transactions . Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4),

Detailed Explanation

The problem asks us to find the maximum profit achievable by buying and selling a stock at most two times, given an array of prices where `prices[i]` is the price of the stock on the i-th day. A crucial constraint is that you cannot hold two stocks simultaneously, meaning you must sell before buying again. The input is the `prices` array, and the output is the maximum profit.

Solution Approach

The solution utilizes a dynamic programming approach with constant space. It iterates through the `prices` array and updates four variables: `buy1`, `sell1`, `buy2`, and `sell2`. `buy1` stores the minimum cost of buying the first stock. `sell1` stores the maximum profit after the first transaction. `buy2` stores the minimum cost of buying the second stock after the first transaction. `sell2` stores the maximum profit after the second transaction. By iterating through the prices and updating these variables appropriately, the final `sell2` will hold the maximum profit that can be achieved with at most two transactions.

Step-by-Step Algorithm

Step 1: Initialize `buy1` and `buy2` to negative infinity (or INT_MIN) because we want to minimize the cost when we buy stock, starting with the lowest possible value. Initialize `sell1` and `sell2` to 0 because initially, we have no profit.
Step 2: Iterate through the `prices` array.
Step 3: In each iteration, update `sell2` as the maximum of its current value and `buy2 + price` (selling the second stock at the current price).
Step 4: Update `buy2` as the maximum of its current value and `sell1 - price` (buying the second stock at the current price after making profit `sell1` from the first transaction).
Step 5: Update `sell1` as the maximum of its current value and `buy1 + price` (selling the first stock at the current price).
Step 6: Update `buy1` as the maximum of its current value and `-price` (buying the first stock at the current price. Initial investment will be negative).
Step 7: After iterating through all prices, return `sell2`, which represents the maximum profit achievable with at most two transactions.

Key Insights

Insight 1: We can think of the problem as finding the best split point in the `prices` array and maximizing profit from the left and right subarrays independently. However, iterating through all split points would be O(n^2).
Insight 2: The optimal solution avoids explicitly splitting the array. Instead, it uses dynamic programming with constant space to track the maximum profit after at most two transactions by maintaining four variables: buy1, sell1, buy2, and sell2, representing buying the first stock, selling the first stock, buying the second stock, and selling the second stock respectively.
Insight 3: The key to the O(n) solution lies in updating these four variables in the correct order in each iteration. The `buy1` and `sell1` always represents at most one transaction and `buy2` and `sell2` represents at most two transactions.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming.

Companies

Asked at: Bolt, Citadel, Groww, PhonePe, Snap, Tekion, TikTok, Uber, Visa.

Best Time to Buy and Sell Stock III | LeetCode 123

Hard

Array Dynamic Programming

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

Solution Code

Available in:

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE;
        int sell2 = 0;

        for (int price : prices) {
            sell2 = Math.max(sell2, buy2 + price);
            buy2 = Math.max(buy2, sell1 - price);
            sell1 = Math.max(sell1, buy1 + price);
            buy1 = Math.max(buy1, -price);
        }
        
        return sell2;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 123: Best Time to Buy and Sell Stock III - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming

Companies

BoltCitadelGrowwPhonePeSnapTekionTikTokUber

Stats

Difficulty:Hard

Languages:4

Companies:9

Problem #:123

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

7 steps

1
Step 1: Initialize `buy1` and `buy2` to negative infinity (or INT_MIN) because we want to minimize the cost when we buy stock, starting with the lowest possible value. Initialize `sell1` and `sell2` to 0 because initially, we have no profit.
2
Step 2: Iterate through the `prices` array.
3
Step 3: In each iteration, update `sell2` as the maximum of its current value and `buy2 + price` (selling the second stock at the current price).
4
Step 4: Update `buy2` as the maximum of its current value and `sell1 - price` (buying the second stock at the current price after making profit `sell1` from the first transaction).
5
Step 5: Update `sell1` as the maximum of its current value and `buy1 + price` (selling the first stock at the current price).
6
Step 6: Update `buy1` as the maximum of its current value and `-price` (buying the first stock at the current price. Initial investment will be negative).
7
Step 7: After iterating through all prices, return `sell2`, which represents the maximum profit achievable with at most two transactions.

💡

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 directly proportional to the number of elements in the `prices` array due to the single loop. The space complexity remains constant because we are only using a fixed number of variables, and their memory usage doesn't depend on the size of the input array.

📖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 2D Array

A more intuitive DP approach involves creating a 2D array `dp[k][i]` where `k` is the number of transactions (0 to 2) and `i` is the day (0 to n-1). `dp[k][i]` stores the maximum profit achievable with at most `k` transactions up to day `i`. However, this solution has O(n*k) time complexity and O(n*k) space complexity where k is the allowed number of transactions.

Time: O(n*k), where n is the number of days and k is the number of transactions.Space: O(n*k)

Trade-offs: While more intuitive, this approach has higher space complexity compared to the O(1) space solution and it's only viable when `k` is relatively small.

✨

Key Insights

1Insight 1: We can think of the problem as finding the best split point in the `prices` array and maximizing profit from the left and right subarrays independently. However, iterating through all split points would be O(n^2).
2Insight 2: The optimal solution avoids explicitly splitting the array. Instead, it uses dynamic programming with constant space to track the maximum profit after at most two transactions by maintaining four variables: buy1, sell1, buy2, and sell2, representing buying the first stock, selling the first stock, buying the second stock, and selling the second stock respectively.
3Insight 3: The key to the O(n) solution lies in updating these four variables in the correct order in each iteration. The `buy1` and `sell1` always represents at most one transaction and `buy2` and `sell2` represents at most two transactions.

📚

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.

Edge Cases

Edge case 1: Empty `prices` array. The code handles this correctly because the loop will not execute, and the initialized value of `sell2` (which is 0) will be returned. This is the correct output for an empty array.
Edge case 2: `prices` array is monotonically decreasing (e.g., [7, 6, 5, 4, 3, 1]). In this case, no profitable transaction is possible. The algorithm will correctly return 0 because `buy1`, `sell1`, `buy2`, and `sell2` will be updated to reflect no profitable trades.
Edge case 3: `prices` array is monotonically increasing. The solution will correctly calculate the profit by buying on the first day and selling on the last day if the array has more than one element. For example `[1,2,3,4,5]`

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrect initialization of `buy1` and `buy2` to 0 instead of negative infinity. This can lead to incorrect profit calculations because the initial 'buy' price would be artificially low.

✗Common mistake 2: Updating the `buy` and `sell` variables in the wrong order. Specifically, `sell2` must be updated before `buy2`, and `sell1` must be updated before `buy1`. Otherwise, you would use the same day's price for both transactions, violating the 'no simultaneous transactions' constraint.

✗Common mistake 3: Incorrectly assuming that buying on the lowest price day and selling on the highest price day will automatically give you max profit. This will fail when there are more than one transaction

✅

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. Optimizing buy/sell strategies in stock markets with transaction limits.

🏦Real-world scenario 2: Resource allocation. Maximizing profit from buying and selling resources with limited transaction opportunities.

💡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

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ 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: October 2, 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

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

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

@TechLeadJul 7

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

@DevExpert92Jun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Best Time to Buy and Sell Stock III"?

For this hard-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?