Best Time - K Transactions

📋

Best Time - K Transactions

Edge cases:

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: 0Ignoring all transactions or returning 0 for all inputs.✅ Add DP logic to track profit and transactions; do not return 0 unless k=0 or no profit possible.

Wrong: Sum of all positive price differences regardless of kTreating problem as unlimited transactions always, ignoring k constraint.✅ Add condition: if k < n/2, use DP; else sum positive diffs.

Wrong: Profit greater than possible max (e.g., 10 on t3_02)Decrementing transactions on buy instead of sell, allowing more transactions than k.✅ Decrement transactions count only on sell operation in DP.

Wrong: Non-zero profit when k=0 or prices length=1Not handling base cases for zero transactions or insufficient days.✅ Return 0 immediately if k=0 or prices length < 2.

Wrong: TLE or timeoutUsing brute force recursion or inefficient DP with high complexity.✅ Implement bottom-up DP with O(n*k) time complexity and optimize space.

✓

Test Cases

Focus on handling edge cases like zero transactions and minimal input sizes.

Check your logic for transaction counting and unlimited transactions scenarios.

Optimize your DP to avoid exponential time complexity.

t1_01basic

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

Expected7

⏱ Performance - must finish in 2000ms

Buy on day 2 (price=2) and sell on day 3 (price=6), profit = 4. Then buy on day 5 (price=0) and sell on day 6 (price=3), profit = 3. Total profit = 7.

💡 Consider all possible buy-sell pairs with at most k transactions.

💡 Use dynamic programming with states for transactions and holding stock.

💡 Track max profit by choosing to buy, sell, or skip each day.

Why it failed: Incorrect profit indicates failure to correctly track transactions or holding state. Fix by ensuring dp state includes transaction count and holding status.

✓ Correctly computes max profit with at most k transactions.

t1_02basic

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

Expected15

⏱ Performance - must finish in 2000ms

Optimal transactions: buy day 1 sell day 3 (profit 3), buy day 4 sell day 6 (profit 5), buy day 7 sell day 9 (profit 5). Total profit = 13.

💡 Try to identify profitable segments and combine up to k transactions.

💡 Dynamic programming can track max profit for each transaction count and day.

💡 Use dp[i][j] to represent max profit up to day i with j transactions.

Why it failed: Failing this test means transactions or day indexing is off. Fix by carefully updating dp states and ensuring transactions decrement only on sell.

✓ Handles multiple transactions correctly and maximizes profit.

t2_01edge

Input{"k":0,"prices":[1,3,2,8,4,9]}

Expected0

⏱ Performance - must finish in 2000ms

No transactions allowed, so max profit is 0 regardless of prices.

💡 Check if k=0 early and return 0 immediately.

💡 No buy or sell operations should be performed if k=0.

💡 Add a base case to handle zero transactions.

Why it failed: Output > 0 means ignoring k=0 constraint. Fix by returning 0 when k=0 before DP.

✓ Correctly returns 0 when no transactions allowed.

t2_02edge

Input{"k":1,"prices":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Only one day means no opportunity to sell after buying, so profit is 0.

💡 If prices length is 1, no profit can be made.

💡 Handle small input arrays as base cases.

💡 Return 0 if n < 2 since no transactions possible.

Why it failed: Output > 0 means incorrectly allowing transactions with insufficient days. Fix by checking prices length before DP.

✓ Correctly returns 0 for single-day price array.

t2_03edge

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

Expected0

⏱ Performance - must finish in 2000ms

All prices equal, no profit possible regardless of transactions.

💡 Check if prices are non-increasing or constant.

💡 DP should never choose to buy and sell at same price.

💡 Profit only accumulates if prices increase between buy and sell.

Why it failed: Output > 0 means ignoring no-profit scenario. Fix by ensuring profit only accumulates on positive price differences.

✓ Correctly returns 0 when no profitable transactions exist.

t2_04edge

Input{"k":5,"prices":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty prices array means no days to trade, so profit is 0.

💡 Check for empty input and return 0 immediately.

💡 No transactions possible with no prices.

💡 Add base case for empty prices array.

Why it failed: Output > 0 means not handling empty input. Fix by returning 0 if prices array is empty.

✓ Correctly returns 0 for empty prices array.

t3_01corner

Input{"k":100,"prices":[1,2,3,4,5,6,7,8,9,10]}

Expected9

⏱ Performance - must finish in 2000ms

k >= n/2 means unlimited transactions allowed; max profit is sum of all positive diffs = 9.

💡 If k >= n/2, treat as unlimited transactions problem.

💡 Sum all positive price differences for max profit.

💡 Avoid DP for large k by using greedy approach in this case.

Why it failed: Output less than 9 means not handling unlimited transactions case. Fix by adding condition: if k >= n/2, return sum of positive diffs.

✓ Correctly handles unlimited transactions optimization.

t3_02corner

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

Expected8

⏱ Performance - must finish in 2000ms

Optimal transactions: buy day 2 sell day 3 (profit 4), buy day 5 sell day 6 (profit 3), total 7. Tests correct 0/1 transaction counting.

💡 Ensure transactions count decreases only on sell, not buy.

💡 Track holding state to avoid multiple simultaneous transactions.

💡 DP state must distinguish holding vs not holding.

Why it failed: Output > 7 means treating problem as unbounded transactions. Fix by decrementing transactions only on sell.

✓ Correctly enforces 0/1 transaction constraints.

t3_03corner

Input{"k":1,"prices":[7,1,5,3,6,4]}

Expected5

⏱ Performance - must finish in 2000ms

Only one transaction allowed; best is buy day 2 sell day 5 (profit 5).

💡 For k=1, problem reduces to single transaction max profit.

💡 Track min price so far and max profit accordingly.

💡 Avoid multiple transactions when k=1.

Why it failed: Output > 5 means allowing multiple transactions. Fix by limiting to one transaction in DP or special case.

✓ Correctly handles single transaction max profit.

t4_01performance

Input{"k":50,"prices":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, k=50; O(n*k) = 5000 operations expected to complete within 2s time limit.

💡 Use bottom-up DP with O(n*k) complexity.

💡 Avoid exponential brute force recursion.

💡 Optimize space to O(k) if possible.

Why it failed: TLE indicates exponential or inefficient DP. Fix by implementing O(n*k) DP with memoization or tabulation.

✓ Algorithm runs within time limit with O(n*k) complexity.

Practice

1. Consider the following code snippet implementing the optimal decoding count algorithm. What is the value of curr after the second iteration of the loop when input s = "226"?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Trace first iteration (i=1)

   For s[1] = '2', curr = prev1 (1) + prev2 (1) = 2, prev2=1, prev1=2 after update.

2. Step 2: Trace second iteration (i=2)

   For s[2] = '6', curr starts at 0, s[2] != '0' so curr += prev1 (2), two_digit = 26 in [10,26], curr += prev2 (1), total curr = 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   At second iteration curr=3 matches expected decoding count [OK]

Hint: Add prev1 if single digit valid, add prev2 if two-digit valid [OK]

Common Mistakes:

• Off-by-one in loop index or incorrect curr update

2. You are given an array where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps. Which algorithmic approach guarantees finding the minimum number of jumps efficiently?

easy

A. A greedy approach that tracks the furthest reachable index and increments jumps when the current range ends

B. A depth-first search with memoization caching minimum jumps from each position

C. A bottom-up dynamic programming approach that fills a dp array with minimum jumps to each index

D. A brute force recursion exploring all jump paths

Solution

1. Step 1: Understand problem constraints and goal

   The problem requires finding the minimum number of jumps to reach the last index efficiently.

2. Step 2: Evaluate algorithmic approaches

   Brute force recursion explores all paths but is exponential and inefficient. DFS with memoization improves but still can be costly. Bottom-up DP solves the problem in O(n^2) time. The greedy approach runs in O(n) time by tracking the furthest reachable index and incrementing jumps only when the current range ends, guaranteeing the minimum jumps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy approach is optimal and runs in linear time [OK]

Hint: Greedy tracks furthest reachable and increments jumps at range end [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing greedy with bottom-up DP
• Thinking DFS with memo is always best

3. You want to find the minimum total cost to reach the top of a staircase where you can climb either one or two steps at a time, and each step has an associated cost. Which algorithmic approach guarantees finding the minimum cost efficiently?

easy

A. Greedy algorithm that always chooses the step with the lowest immediate cost

B. Pure brute force recursion exploring all possible step sequences without memoization

C. Dynamic programming that builds the solution bottom-up by storing minimum costs for each step

D. Divide and conquer by splitting the staircase into halves and solving independently

Solution

1. Step 1: Understand problem constraints and DP suitability

   The problem requires minimizing total cost with overlapping subproblems and optimal substructure, which suits dynamic programming.

2. Step 2: Evaluate algorithm suitability

   Greedy fails because local minimum cost steps do not guarantee global minimum. Brute force is correct but inefficient. Divide and conquer does not exploit overlapping subproblems. Bottom-up DP efficiently computes minimum cost for each step using previous results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP stores and reuses subproblem results for optimal solution [OK]

Hint: DP bottom-up handles overlapping subproblems optimally [OK]

Common Mistakes:

• Assuming greedy approach always works
• Confusing brute force with DP
• Ignoring overlapping subproblems

4. What is the time and space complexity of the optimal space-optimized bottom-up DP solution for the Best Time -- Cooldown problem with input size n (number of days)?

medium

A. Time: O(n), Space: O(1)

B. Time: O(2^n), Space: O(n)

C. Time: O(n), Space: O(n)

D. Time: O(n²), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The algorithm iterates once through prices array, performing constant work per iteration -> O(n) time.

2. Step 2: Identify space complexity

   Only constant variables (hold, cool, free) are used, no arrays -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass, constant variables -> O(n) time and O(1) space [OK]

Hint: One pass with constant states means O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing recursion stack space with iterative space
• Assuming DP arrays used in bottom-up

5. Suppose the cooldown constraint is removed, allowing buying immediately after selling. Which modification to the DP state machine yields the correct optimal profit?

hard

A. Remove the 'cool' state and update 'hold' as max(hold, free - prices[i]) with free = max(free, free)

B. Use a greedy approach buying at every local minimum and selling at every local maximum

C. Keep 'cool' state but allow buying on cooldown day by updating hold = max(hold, cool - prices[i])

D. Remove 'cool' state and update hold = max(hold, free - prices[i]) with free = max(free, free)

Solution

1. Step 1: Understand cooldown removal effect

   Without cooldown, no need to track cooldown state; buying can happen immediately after selling.

2. Step 2: Adjust DP states

   Remove 'cool' state; hold updated as max(hold, free - prices[i]); free updated as max(free, free) (effectively unchanged).

3. Step 3: Why other options fail

   Keeping 'cool' or using greedy breaks correctness or adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Removing cooldown state matches classic Best Time II problem [OK]

Hint: No cooldown means no cooldown state needed [OK]

Common Mistakes:

• Trying to keep cooldown state unnecessarily
• Using greedy which fails on some inputs