Best Time - 2 Transactions

📋

Best Time - 2 Transactions

Edge cases:

</>

IDE

def maxProfit(prices: list[int]) -> int:public int maxProfit(int[] prices)int maxProfit(vector<int> &prices)function maxProfit(prices)

def maxProfit(prices):
    # Write your solution here
    pass

class Solution {
    public int maxProfit(int[] prices) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxProfit(vector<int> &prices) {
    // Write your solution here
    return 0;
}

function maxProfit(prices) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning zero profit for all inputs due to missing transaction logic or incorrect base case handling.✅ Add proper DP initialization and update logic to compute profits from transactions.

Wrong: less than expected max profitGreedy approach picking local maxima without considering global optimal two transactions.✅ Use DP state machine or prefix/suffix max profit arrays to combine two transactions correctly.

Wrong: greater than expected max profitTreating problem as unlimited transactions instead of at most two, summing all positive differences.✅ Add transaction count state in DP to limit to two transactions.

Wrong: crash or errorNot handling empty or single-element input arrays properly.✅ Add guard clauses for empty or small inputs returning 0.

Wrong: TLEUsing brute force or high complexity DP on large inputs.✅ Implement O(n) DP with constant space states for two transactions.

✓

Test Cases

Make sure your solution handles empty and minimal inputs correctly.

Focus on enforcing the two transaction limit and avoiding greedy mistakes.

Optimize your DP to linear time and constant space for large inputs.

t1_01basic

Input{"prices":[3,3,5,0,0,3,1,4]}

Expected6

⏱ Performance - must finish in 2000ms

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.

💡 Consider splitting the problem into two parts: max profit before day i and max profit after day i.

💡 Use dynamic programming to track max profit with at most one transaction up to each day and from each day to the end.

💡 Combine these two arrays to find the max sum of two transactions.

Why it failed: Incorrect output means the solution likely does not correctly handle two transactions or overlaps them. Fix by ensuring transactions do not overlap and use DP arrays for prefix and suffix profits.

✓ Correctly handles two transactions with proper DP state management.

t1_02basic

Input{"prices":[1,2,4,2,5,7,2,4,9,0]}

Expected13

⏱ Performance - must finish in 2000ms

Best two transactions: buy at 1 sell at 7 (profit 6), buy at 2 sell at 9 (profit 7), total 13.

💡 Track max profit from left to right and right to left separately.

💡 Use prefix max profit and suffix max profit arrays to combine results.

💡 Sum prefix and suffix profits at each day to find max total profit.

Why it failed: If output is less than 13, solution likely misses combining two transactions optimally. Fix by computing prefix and suffix max profits and summing them correctly.

✓ Correctly computes max profit with two transactions using prefix and suffix DP.

t2_01edge

Input{"prices":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty prices array means no transactions possible, profit is 0.

💡 Check how your code handles empty input arrays.

💡 Ensure base case returns 0 when prices length is 0.

💡 Add a guard clause to return 0 if prices is empty.

Why it failed: Code crashes or returns non-zero on empty input. Fix by adding a check: if not prices: return 0.

✓ Handles empty input gracefully with zero profit.

t2_02edge

Input{"prices":[1]}

Expected0

⏱ Performance - must finish in 2000ms

Only one day means no buy-sell pair possible, profit is 0.

💡 Consider minimum input size and that no transaction can occur with one price.

💡 Check that your DP or loops handle single-element arrays without error.

💡 Return 0 if prices length is less than 2.

Why it failed: Returns non-zero profit for single day input. Fix by ensuring transactions require at least two days.

✓ Correctly returns zero profit for single day input.

t2_03edge

Input{"prices":[5,4,3,2,1]}

Expected0

⏱ Performance - must finish in 2000ms

Prices strictly decreasing, no profitable transactions possible, profit is 0.

💡 Check that your solution does not count negative profits as positive.

💡 Ensure max profit is never less than zero.

💡 Use max(0, profit) when calculating transaction profits.

Why it failed: Returns negative or positive profit incorrectly on decreasing prices. Fix by clamping profit to zero when negative.

✓ Correctly returns zero profit for decreasing prices.

t2_04edge

Input{"prices":[2,2,2,2,2]}

Expected0

⏱ Performance - must finish in 2000ms

All prices identical, no profit possible, profit is 0.

💡 Check that your solution handles flat price arrays correctly.

💡 Ensure no transactions are made if profit is zero.

💡 Return 0 if no profitable transactions found.

Why it failed: Returns positive profit on flat prices. Fix by ensuring profit calculation does not count zero or negative gains.

✓ Correctly returns zero profit for identical prices.

t3_01corner

Input{"prices":[1,2,3,4,5]}

Expected4

⏱ Performance - must finish in 2000ms

Only one transaction needed: buy at 1, sell at 5, profit 4. Two transactions allowed but one is optimal.

💡 Check if your solution unnecessarily splits one transaction into two.

💡 Verify that the DP allows zero or one transaction if better than two.

💡 Ensure max profit is max of one transaction or two transactions.

Why it failed: Returns profit less than 4 due to greedy splitting or incorrect DP states. Fix by allowing zero or one transaction if better than two.

✓ Correctly handles cases where one transaction is optimal despite allowance for two.

t3_02corner

Input{"prices":[3,2,6,5,0,3]}

Expected7

⏱ Performance - must finish in 2000ms

Best two transactions: buy at 2 sell at 6 (profit 4), buy at 0 sell at 3 (profit 3), total 7.

💡 Beware of greedy approaches that pick local maxima without global optimization.

💡 Use DP to track states of transactions and holding/not holding stock.

💡 Implement state machine DP with states: no stock 0, holding stock 1, after first sell 2, holding second stock 3, after second sell 4.

Why it failed: Greedy solutions may return 6 or less by missing optimal second transaction. Fix by using DP state machine to track transactions.

✓ Correctly computes max profit using DP state machine avoiding greedy traps.

t3_03corner

Input{"prices":[1,2,4,2,5,7,2,4,9,0]}

Expected13

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded transactions; only two transactions allowed, not unlimited.

💡 Check that your solution limits transactions to at most two.

💡 Avoid summing all positive differences as if unlimited transactions allowed.

💡 Use DP with transaction count state to enforce max two transactions.

Why it failed: Returns profit greater than 13 by treating problem as unlimited transactions. Fix by adding transaction count limit in DP states.

✓ Correctly enforces max two transactions constraint.

t4_01performance

Input{"prices":[99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901,99900]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100000 with descending prices; O(n) DP solution must complete within 2 seconds.

💡 Brute force O(n^4) will time out on large inputs.

💡 Use O(n) DP with state machine for at most two transactions.

💡 Optimize space by tracking only necessary states per day.

Why it failed: TLE due to using brute force or inefficient DP. Fix by implementing O(n) DP with constant space states.

✓ Efficient O(n) DP solution passes performance test.

Practice

1. You are given a list of daily stock prices and a maximum number of allowed transactions. You want to maximize profit by buying and selling stocks, but you cannot hold more than one stock at a time and must complete each transaction before starting another. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer splitting the price array and merging results

B. Greedy algorithm that buys whenever price is lower than the next day and sells the next day

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Dynamic programming using state machines to track buy/sell states for each transaction count

Solution

1. Step 1: Understand problem constraints and limitations of greedy

   The problem limits the number of transactions and requires maximizing profit with buy/sell states, which greedy fails to handle optimally.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks holding and not holding states per transaction count, ensuring all possibilities are considered efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy fails on multiple transactions; DP state machines handle all cases [OK]

Hint: DP with states handles transaction limits optimally [OK]

Common Mistakes:

• Assuming greedy always works for stock problems

2. Consider the following Python code for climbing stairs:

def climb_stairs(n):
    if n <= 1:
        return 1
    first, second = 1, 1
    for _ in range(2, n + 1):
        current = first + second
        first, second = second, current
    return second

print(climb_stairs(4))

What is the value of the variable current during the last iteration of the loop?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace variable values for n=4

   Initialize first=1, second=1. Iterations: - i=2: current=1+1=2; first=1, second=2 - i=3: current=1+2=3; first=2, second=3 - i=4: current=2+3=5; first=3, second=5

2. Step 2: Identify last iteration's current value

   The last iteration is i=4, current=5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Last current computed is 5 for n=4 [OK]

Hint: Trace loop iterations carefully to find current value [OK]

Common Mistakes:

• Confusing loop bounds and off-by-one errors
• Returning previous current instead of last

3. You are given a list of non-negative integers representing the amount of money in each house along a street. You want to maximize the total amount you can rob tonight without robbing two adjacent houses. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming that considers robbing or skipping each house to maximize total

B. A greedy algorithm that always picks the house with the maximum amount next

C. Sorting the houses by amount and picking the top half

D. Depth-first search exploring all subsets of houses

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum without robbing adjacent houses, which is a classic overlapping subproblems scenario.

2. Step 2: Identify suitable algorithm

   Dynamic programming fits because it explores choices at each house (rob or skip) and uses previous results to build optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on cases like [2,7,9,3,1], DP finds max 12 [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Greedy approach fails on non-adjacent constraints

4. The following code attempts to solve the Jump Game problem optimally. Which line contains a subtle bug that causes incorrect results on edge cases like [0] or [3,2,1,0,4]?

def canJump(nums):
    maxReach = 0
    n = len(nums)
    for i in range(n):
        if i >= maxReach:
            return False
        maxReach = max(maxReach, i + nums[i])
        if maxReach >= n - 1:
            return True
    return False

medium

A. Line 4: for i in range(n):

B. Line 6: maxReach = max(maxReach, i + nums[i])

C. Line 5: if i >= maxReach:

D. Line 8: return False

Solution

1. Step 1: Analyze base case handling

   For input [0], i=0 and maxReach=0, so condition i >= maxReach is True, causing premature return False.

2. Step 2: Identify correct condition

   The condition should be i > maxReach to allow starting position when maxReach=0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing to i > maxReach fixes base case and edge failures [OK]

Hint: Check boundary conditions for i and maxReach carefully [OK]

Common Mistakes:

• Using >= instead of > in reachability check
• Ignoring single-element array base case
• Assuming greedy always works without proof

5. Suppose the problem changes so you can climb 1, 2, or 3 steps at a time. Which modification to the bottom-up DP approach correctly computes the minimum cost to reach the top?

hard

A. Change the recurrence to curr = cost[i] + min(prev1, prev2) and keep the same loop

B. Keep the original code but run the loop until n+1 to cover extra steps

C. Use a greedy approach picking the cheapest next step among 1, 2, or 3 steps

D. Change the recurrence to curr = cost[i] + min(prev1, prev2, prev3) and track three previous states

Solution

1. Step 1: Understand new step options

   With 1, 2, or 3 steps allowed, the cost to reach step i depends on the minimum cost to reach steps i-1, i-2, and i-3.

2. Step 2: Modify DP recurrence and state tracking

   Track three previous states (prev1, prev2, prev3) and compute curr = cost[i] + min(prev1, prev2, prev3) to cover all possibilities.

3. Step 3: Reject incorrect options

   Change the recurrence to curr = cost[i] + min(prev1, prev2) and keep the same loop ignores the third previous step, greedy fails to guarantee global minimum, and extending loop without updating recurrence is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DP recurrence must consider all allowed step sizes [OK]

Hint: Include all allowed previous steps in min calculation [OK]

Common Mistakes:

• Ignoring new step size in recurrence
• Using greedy instead of DP
• Extending loop without recurrence update