What happens if you not handling the case when k >= n/2?

Solution times out or uses unnecessary DP for unlimited transactions Fix: Add a shortcut to sum all positive price differences when k is large

What happens if you mixing up holding and not holding states?

Incorrect profit calculations and wrong answers Fix: Carefully track and update dp states for holding and not holding separately

What happens if you iterating forwards in space optimized dp?

Overwrites dp values prematurely, causing incorrect results Fix: Iterate backwards over transactions to preserve previous states

What happens if you forgetting to reduce transactions count when buying?

Overcounts transactions leading to invalid solutions Fix: Decrease transactions count only when selling (completing a transaction)

Interview Prepdp-linear-fibonaccihardAmazonGoogle

Best Time - K Transactions

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

hardDPAmazonGoogle

Imagine you are a stock trader who can make at most K buy-sell transactions to maximize profit over a series of days. How do you decide when to buy and sell?

💡 This problem is a classic example of dynamic programming where beginners struggle because of the multiple states involved: days, transactions left, and holding status. Understanding the state transitions is key.

📋

Problem Statement

Given an integer array prices where prices[i] is the price of a given stock on the i-th day, and an integer k representing the maximum number of transactions allowed, find the maximum profit you can achieve. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Return the maximum profit achievable with at most k transactions.

1 ≤ prices.length ≤ 10^50 ≤ prices[i] ≤ 10^50 ≤ k ≤ 10^9

💡

Example

Input"k = 2, prices = [3,2,6,5,0,3]"

Output7

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.

Input"k = 2, prices = [2,4,1]"

Output2

Buy on day 1 (price=2) and sell on day 2 (price=4), profit = 2. No second transaction needed.

k = 0 → output 0 (no transactions allowed)
prices array length = 1 → output 0 (only one day, no profit possible)
k >= n/2 → treat as unlimited transactions problem
prices all equal → output 0 (no profit possible)

🔁

Why DP?

Why greedy fails:

A greedy approach that buys low and sells high locally fails because it doesn't consider the limit on the number of transactions. For example, buying and selling every profitable pair might exceed k transactions, leading to invalid solutions.

DP state:

dp[i][j][0 or 1] represents the maximum profit on day i with at most j transactions completed, where 0 means not holding stock and 1 means holding stock.

Recurrence:

dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

On day i, if not holding stock, either we did nothing or sold today. If holding stock, either we did nothing or bought today (using one transaction).

⚠️

Common Mistakes

Not handling the case when k >= n/2

Solution times out or uses unnecessary DP for unlimited transactions

✅ Add a shortcut to sum all positive price differences when k is large

Mixing up holding and not holding states

Incorrect profit calculations and wrong answers

✅ Carefully track and update dp states for holding and not holding separately

Iterating forwards in space optimized DP

Overwrites dp values prematurely, causing incorrect results

✅ Iterate backwards over transactions to preserve previous states

Forgetting to reduce transactions count when buying

Overcounts transactions leading to invalid solutions

✅ Decrease transactions count only when selling (completing a transaction)

Using 3D DP without memoization or tabulation

Exponential time complexity and TLE

✅ Use memoization or bottom-up DP to avoid recomputation

🧠

Brute Force (Pure Recursion)

💡 This approach explores all possible buy/sell decisions on each day, which helps understand the problem's exponential nature and why optimization is necessary.

Intuition

Try every possible transaction sequence by deciding to buy, sell, or skip on each day, tracking transactions left and holding state.

Algorithm

Define a recursive function with parameters: current day, transactions left, and holding state.
If no days left or no transactions left, return 0 profit.
If holding stock, decide to sell or skip.
If not holding, decide to buy or skip.
Return the maximum profit from these choices.

💡 The recursion tree grows exponentially because each day has multiple choices, making it inefficient but conceptually clear.

Recurrence:

f(i, k, holding) = max(
  if holding: max(f(i+1, k, holding), f(i+1, k-1, not holding) + prices[i]),
  else: max(f(i+1, k, holding), f(i+1, k, holding) - prices[i])
)

</>

Code

def maxProfit(k, prices):
    n = len(prices)
    def dfs(i, transactions_left, holding):
        if i == n or transactions_left == 0:
            return 0
        if holding:
            sell = dfs(i + 1, transactions_left - 1, False) + prices[i]
            skip = dfs(i + 1, transactions_left, True)
            return max(sell, skip)
        else:
            buy = dfs(i + 1, transactions_left, True) - prices[i]
            skip = dfs(i + 1, transactions_left, False)
            return max(buy, skip)
    return dfs(0, k, False)

# Example usage
if __name__ == '__main__':
    print(maxProfit(2, [3,2,6,5,0,3]))  # Output: 7

Line Notes

def dfs(i, transactions_left, holding):Defines recursive function with day, transactions left, and holding state

if i == n or transactions_left == 0:Base case: no days or no transactions left means no profit

if holding:If currently holding stock, can sell or skip

sell = dfs(i + 1, transactions_left - 1, False) + prices[i]Sell stock today, gain price, reduce transactions

buy = dfs(i + 1, transactions_left, True) - prices[i]Buy stock today, spend price, holding becomes True

return dfs(0, k, False)Start recursion from day 0, with k transactions, not holding stock

public class Solution {
    public int maxProfit(int k, int[] prices) {
        return dfs(prices, 0, k, false);
    }
    private int dfs(int[] prices, int i, int transactionsLeft, boolean holding) {
        if (i == prices.length || transactionsLeft == 0) return 0;
        if (holding) {
            int sell = dfs(prices, i + 1, transactionsLeft - 1, false) + prices[i];
            int skip = dfs(prices, i + 1, transactionsLeft, true);
            return Math.max(sell, skip);
        } else {
            int buy = dfs(prices, i + 1, transactionsLeft, true) - prices[i];
            int skip = dfs(prices, i + 1, transactionsLeft, false);
            return Math.max(buy, skip);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(2, new int[]{3,2,6,5,0,3})); // 7
    }
}

Line Notes

public int maxProfit(int k, int[] prices)Entry point calling recursive dfs

if (i == prices.length || transactionsLeft == 0) return 0;Base case: no days or no transactions left

if (holding)If holding stock, decide to sell or skip

int sell = dfs(prices, i + 1, transactionsLeft - 1, false) + prices[i];Sell stock today, gain price, reduce transactions

int buy = dfs(prices, i + 1, transactionsLeft, true) - prices[i];Buy stock today, spend price, holding becomes true

System.out.println(sol.maxProfit(2, new int[]{3,2,6,5,0,3}));Test example prints expected output

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

int dfs(const vector<int>& prices, int i, int transactionsLeft, bool holding) {
    if (i == prices.size() || transactionsLeft == 0) return 0;
    if (holding) {
        int sell = dfs(prices, i + 1, transactionsLeft - 1, false) + prices[i];
        int skip = dfs(prices, i + 1, transactionsLeft, true);
        return max(sell, skip);
    } else {
        int buy = dfs(prices, i + 1, transactionsLeft, true) - prices[i];
        int skip = dfs(prices, i + 1, transactionsLeft, false);
        return max(buy, skip);
    }
}

int maxProfit(int k, vector<int>& prices) {
    return dfs(prices, 0, k, false);
}

int main() {
    vector<int> prices = {3,2,6,5,0,3};
    cout << maxProfit(2, prices) << endl; // 7
    return 0;
}

Line Notes

int dfs(const vector<int>& prices, int i, int transactionsLeft, bool holding)Recursive function with day, transactions left, holding state

if (i == prices.size() || transactionsLeft == 0) return 0;Base case: no days or no transactions left

if (holding)If holding stock, choose to sell or skip

int sell = dfs(prices, i + 1, transactionsLeft - 1, false) + prices[i];Sell stock today, gain price, reduce transactions

int buy = dfs(prices, i + 1, transactionsLeft, true) - prices[i];Buy stock today, spend price, holding becomes true

cout << maxProfit(2, prices) << endl;Print result for example test

function maxProfit(k, prices) {
    const n = prices.length;
    function dfs(i, transactionsLeft, holding) {
        if (i === n || transactionsLeft === 0) return 0;
        if (holding) {
            const sell = dfs(i + 1, transactionsLeft - 1, false) + prices[i];
            const skip = dfs(i + 1, transactionsLeft, true);
            return Math.max(sell, skip);
        } else {
            const buy = dfs(i + 1, transactionsLeft, true) - prices[i];
            const skip = dfs(i + 1, transactionsLeft, false);
            return Math.max(buy, skip);
        }
    }
    return dfs(0, k, false);
}

console.log(maxProfit(2, [3,2,6,5,0,3])); // 7

Line Notes

function dfs(i, transactionsLeft, holding)Recursive helper with day, transactions left, holding

if (i === n || transactionsLeft === 0) return 0;Base case: no days or no transactions left

if (holding)If holding stock, decide to sell or skip

const sell = dfs(i + 1, transactionsLeft - 1, false) + prices[i];Sell stock today, gain price, reduce transactions

const buy = dfs(i + 1, transactionsLeft, true) - prices[i];Buy stock today, spend price, holding becomes true

console.log(maxProfit(2, [3,2,6,5,0,3]));Print example output

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each day has two choices (buy/sell/skip), leading to exponential calls.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(2^n)`	`O(n) recursion stack`	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	`O(n * k)`	`O(n * k)`	Possible for large n	Yes	Good for explaining optimization over brute force
3. Bottom-Up DP (Tabulation)	`O(n * k)`	`O(n * k)`	No	Yes	Standard approach to code in interviews
4. Space Optimized Bottom-Up DP	`O(n * k)`	`O(k)`	No	No (without extra bookkeeping)	Best for large inputs and memory constraints

Practice

(1/5)

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

3. Examine the following code snippet for climbing stairs:

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

Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line 2: Incorrect base case condition should be 'if n <= 1'

B. Line 4: Loop range should start from 1 instead of 2

C. Line 5: The addition 'first + second' should be 'first - second'

D. Line 6: The tuple assignment order is reversed

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 variable values for n=4

Step 2: Identify last iteration's current value

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in the code

Step 2: Simplify complexity with fixed k

Final Answer:

Quick Check:

Solution

Step 1: Analyze base case condition

Step 2: Correct base case to 'if n <= 1'

Final Answer:

Quick Check:

Solution

Step 1: Analyze loop range for single-element array

Step 2: Check if jumps=0 is correct for single-element input

Final Answer:

Quick Check:

Solution

Step 1: Understand multiple transactions scenario

Step 2: Identify correct algorithm modification

Final Answer:

Quick Check:

Ready to prove it?