What happens if you not handling the 'at most two transactions' constraint correctly?

Incorrect profit calculation, possibly overcounting transactions Fix: Use DP states that track the number of transactions completed

What happens if you forgetting to update maxdiff correctly in tabulation?

DP table values become incorrect, leading to wrong answers Fix: Update maxDiff after dp[i][k-1] is computed for each day

What happens if you not handling edge cases like empty prices array?

Runtime errors or incorrect output Fix: Add checks for empty or minimal input arrays

Interview Prepdp-linear-fibonaccihardAmazonGoogle

Best Time - 2 Transactions

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

hardDPAmazonGoogle

Imagine you are an investor who can buy and sell a stock at most twice to maximize profit. How do you decide the best days to buy and sell?

💡 This problem is a classic example of dynamic programming where beginners often struggle to model multiple transactions and states. Understanding how to track profits with limited transactions is key.

📋

Problem Statement

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). Input: An integer array prices. Output: An integer representing the maximum profit.

1 ≤ prices.length ≤ 10^50 ≤ prices[i] ≤ 10^5

💡

Example

Input"[3,3,5,0,0,3,1,4]"

Output6

Buy on day 4 (price=0), sell on day 6 (price=3), profit=3. Then buy on day 7 (price=1), sell on day 8 (price=4), profit=3. Total profit=6.

prices = [1] → 0 (only one day, no transaction possible)
prices = [5,4,3,2,1] → 0 (prices decreasing, no profit possible)
prices = [1,2,3,4,5] → 4 (best to buy at day 1 and sell at day 5, only one transaction needed)
prices = [1,2,4,2,5,7,2,4,9,0] → 13 (complex case with multiple peaks and valleys)

🔁

Why DP?

Why greedy fails:

A greedy approach that picks local maxima and minima fails because it might miss better global profits by splitting transactions differently. For example, buying low and selling high twice might yield more profit than one big transaction.

DP state:

dp[i][j] represents the maximum profit achievable up to day i with at most j transactions completed.

Recurrence:dp[i][k] = max(dp[i-1][k], max_{j < i}(prices[i] - prices[j] + dp[j][k-1]))

For each day i and transaction count k, either do no transaction today (carry over previous profit) or sell today after buying on some earlier day j plus profit from k-1 transactions before day j.

⚠️

Common Mistakes

Not handling the 'at most two transactions' constraint correctly

Incorrect profit calculation, possibly overcounting transactions

✅ Use DP states that track the number of transactions completed

Forgetting to update maxDiff correctly in tabulation

DP table values become incorrect, leading to wrong answers

✅ Update maxDiff after dp[i][k-1] is computed for each day

Iterating forwards in space-optimized DP causing overwritten states

Incorrect profit values due to using updated states prematurely

✅ Iterate backwards over transactions to preserve previous states

Not handling edge cases like empty prices array

Runtime errors or incorrect output

✅ Add checks for empty or minimal input arrays

Using floating point instead of integers for prices

Precision errors in profit calculations

✅ Use integer types as prices are integers

🧠

Brute Force (Nested Loops)

💡 This approach tries all possible pairs of buy and sell days for two transactions, helping beginners understand the problem's combinatorial nature before optimization.

Intuition

Try every possible pair of transactions by checking all buy-sell pairs twice and pick the maximum profit.

Algorithm

Enumerate all pairs of buy and sell days for the first transaction.
For each first transaction, enumerate all pairs of buy and sell days for the second transaction after the first sell day.
Calculate total profit for these two transactions.
Keep track of the maximum profit found.

💡 This approach is straightforward but inefficient because it checks every possible transaction pair explicitly.

Recurrence:Not applicable for brute force

</>

Code

def maxProfit(prices):
    n = len(prices)
    max_profit = 0
    for i in range(n):
        for j in range(i + 1, n):
            profit1 = prices[j] - prices[i]
            if profit1 < 0:
                profit1 = 0
            for k in range(j + 1, n):
                for l in range(k + 1, n):
                    profit2 = prices[l] - prices[k]
                    if profit2 < 0:
                        profit2 = 0
                    max_profit = max(max_profit, profit1 + profit2)
    return max_profit

# Driver code
if __name__ == '__main__':
    prices = [3,3,5,0,0,3,1,4]
    print(maxProfit(prices))  # Expected output: 6

Line Notes

for i in range(n)Outer loop picks the first buy day for the first transaction to explore all possible start days.

for j in range(i + 1, n)Inner loop picks the sell day for the first transaction ensuring sell day is after buy day.

profit1 = prices[j] - prices[i]Calculate profit for the first transaction; if negative, set to zero as no profit.

for k in range(j + 1, n)Start second transaction after the first sell day to avoid overlapping transactions.

for l in range(k + 1, n)Pick sell day for the second transaction ensuring valid buy-sell order.

profit2 = prices[l] - prices[k]Calculate profit for the second transaction; if negative, set to zero.

max_profit = max(max_profit, profit1 + profit2)Update max profit if current two transactions yield better profit.

public class Solution {
    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int maxProfit = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int profit1 = prices[j] - prices[i];
                if (profit1 < 0) profit1 = 0;
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int profit2 = prices[l] - prices[k];
                        if (profit2 < 0) profit2 = 0;
                        maxProfit = Math.max(maxProfit, profit1 + profit2);
                    }
                }
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {3,3,5,0,0,3,1,4};
        System.out.println(maxProfit(prices)); // Expected output: 6
    }
}

Line Notes

for (int i = 0; i < n; i++)Outer loop selects first buy day to try all possibilities.

for (int j = i + 1; j < n; j++)Inner loop selects first sell day after buy day.

int profit1 = prices[j] - prices[i];Calculate profit for first transaction; zero if negative.

for (int k = j + 1; k < n; k++)Start second transaction after first sell day.

for (int l = k + 1; l < n; l++)Select second sell day after second buy day.

maxProfit = Math.max(maxProfit, profit1 + profit2);Update max profit if current combination is better.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int maxProfit = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int profit1 = prices[j] - prices[i];
            if (profit1 < 0) profit1 = 0;
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    int profit2 = prices[l] - prices[k];
                    if (profit2 < 0) profit2 = 0;
                    maxProfit = max(maxProfit, profit1 + profit2);
                }
            }
        }
    }
    return maxProfit;
}

int main() {
    vector<int> prices = {3,3,5,0,0,3,1,4};
    cout << maxProfit(prices) << endl; // Expected output: 6
    return 0;
}

Line Notes

for (int i = 0; i < n; i++)Select first buy day to try all options.

for (int j = i + 1; j < n; j++)Select first sell day after buy day.

int profit1 = prices[j] - prices[i];Calculate profit for first transaction; zero if negative.

for (int k = j + 1; k < n; k++)Start second transaction after first sell day.

for (int l = k + 1; l < n; l++)Select second sell day after second buy day.

maxProfit = max(maxProfit, profit1 + profit2);Update max profit if better combination found.

function maxProfit(prices) {
    const n = prices.length;
    let maxProfit = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let profit1 = prices[j] - prices[i];
            if (profit1 < 0) profit1 = 0;
            for (let k = j + 1; k < n; k++) {
                for (let l = k + 1; l < n; l++) {
                    let profit2 = prices[l] - prices[k];
                    if (profit2 < 0) profit2 = 0;
                    maxProfit = Math.max(maxProfit, profit1 + profit2);
                }
            }
        }
    }
    return maxProfit;
}

// Test
console.log(maxProfit([3,3,5,0,0,3,1,4])); // Expected output: 6

Line Notes

for (let i = 0; i < n; i++)Outer loop picks first buy day to explore all possibilities.

for (let j = i + 1; j < n; j++)Inner loop picks first sell day after buy day.

let profit1 = prices[j] - prices[i];Calculate profit for first transaction; zero if negative.

for (let k = j + 1; k < n; k++)Start second transaction after first sell day.

for (let l = k + 1; l < n; l++)Select second sell day after second buy day.

maxProfit = Math.max(maxProfit, profit1 + profit2);Update max profit if current two transactions yield better profit.

⏱

Complexity

TimeO(n^4)

SpaceO(1)

Four nested loops over n days lead to O(n^4) time complexity.

💡 For n=10, this means 10,000 operations; for n=100, 100 million operations, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^4)`	`O(1)`	No	Yes	Mention only - never code
2. Memoization	`O(n * k * 2)`	`O(n * k * 2)`	Possible (deep recursion)	Yes	Good to explain, sometimes code
3. Tabulation	`O(n * k)`	`O(n * k)`	No	Yes	Preferred approach to code
4. Space Optimized	`O(n * k)`	`O(k)`	No	No (without extra bookkeeping)	Mention or code if asked for optimization

Practice

(1/5)

1. Given the following code for maxProfit with k=1 and prices = [1, 5, 3], what is the final returned value?

easy

A. 4

B. 5

C. 3

D. 0

5. What is the time complexity of the optimal dynamic programming solution for the House Robber II problem using the space-optimized approach shown below?

def rob_linear(nums, start, end):
    prev, curr = 0, 0
    for i in range(start, end + 1):
        prev, curr = curr, max(curr, prev + nums[i])
    return curr

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))

medium

A. O(n) with constant extra space

B. O(n²) due to nested loops

C. O(2^n) because of recursion without memoization

D. O(n) because each house is processed twice in two linear scans

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace buy and sell arrays for each price

Step 2: Return sell[k]

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Trace variables for input [2,1,1]

Step 2: Return jumps

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in the code

Step 2: Calculate complexity

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in rob_linear

Step 2: Count calls in rob

Step 3: Consider space usage

Final Answer:

Quick Check:

Ready to prove it?