Best Time to Buy Sell IV (K Transactions)

🎯

Best Time to Buy Sell IV (K Transactions)

hardMIXEDAmazonGoogle

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

💡 This problem is about optimizing profit with limited transactions over time. Beginners struggle because it combines multiple constraints and requires careful state tracking, which is not obvious at first glance.

📋

Problem Statement

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

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.

• k = 0 → 0 profit since no transactions allowed
• prices array empty → 0 profit
• k >= n/2 → unlimited transactions allowed, solve with simpler approach
• prices all equal → 0 profit since no gain possible

⚠️

Common Mistakes

Not handling the unlimited transactions case when k >= n/2

Code runs slowly or gives wrong answer for large k

✅ Add a shortcut to solve with simple linear scan for unlimited transactions

Mixing up holding and not holding states in DP

Incorrect profit calculations and wrong final answer

✅ Carefully track holding state and update DP accordingly

Off-by-one errors in indexing transactions or days

Array index errors or incorrect DP results

✅ Double-check loop boundaries and DP array sizes

Not caching or memoizing recursive calls

Exponential time leading to TLE

✅ Implement memoization or switch to tabulation

Forgetting to reduce transactions count after selling

Overcounting transactions and incorrect profit

✅ Decrease transactions left only when selling

🧠

Brute Force (Pure Recursion)

💡 This approach exists to understand the problem's decision space by exploring all possible buy/sell actions recursively, even though it's inefficient.

Intuition

Try every possible day to buy and sell stocks up to k times, recursively exploring all transaction sequences to find the maximum profit.

Algorithm

1. Define a recursive function with parameters: current day, remaining transactions, and holding state.
2. If no days left or no transactions left, return 0 profit.
3. If holding stock, decide to sell or hold.
4. If not holding, decide to buy or skip.
5. Return the max profit from these choices.

💡 The recursion explores all choices at each day and state, which is conceptually simple but leads to exponential time.

</>

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 = prices[i] + dfs(i + 1, transactions_left - 1, False)
            hold = dfs(i + 1, transactions_left, True)
            return max(sell, hold)
        else:
            buy = -prices[i] + dfs(i + 1, transactions_left, True)
            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 tracking 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, decide to sell or hold

sell = prices[i] + dfs(i + 1, transactions_left - 1, False)Selling gains current price and reduces transactions left

hold = dfs(i + 1, transactions_left, True)Option to hold stock without selling

buy = -prices[i] + dfs(i + 1, transactions_left, True)Buying costs current price and changes holding state

skip = dfs(i + 1, transactions_left, False)Skipping buying on this day

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 = prices[i] + dfs(prices, i + 1, transactionsLeft - 1, false);
            int hold = dfs(prices, i + 1, transactionsLeft, true);
            return Math.max(sell, hold);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, true);
            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 for recursion termination

if (holding) {Branch when currently holding stock

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

int hold = dfs(prices, i + 1, transactionsLeft, true);Option to hold stock without selling

int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, true);Buy stock and change holding state

int skip = dfs(prices, i + 1, transactionsLeft, false);Skip buying on this day

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

#include <iostream>
#include <vector>
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 = prices[i] + dfs(prices, i + 1, transactionsLeft - 1, false);
        int hold = dfs(prices, i + 1, transactionsLeft, true);
        return max(sell, hold);
    } else {
        int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, true);
        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, and holding state

if (i == prices.size() || transactionsLeft == 0) return 0;Base case to stop recursion

if (holding) {Branch when holding stock

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

int hold = dfs(prices, i + 1, transactionsLeft, true);Option to hold stock without selling

int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, true);Buy stock and change holding state

int skip = dfs(prices, i + 1, transactionsLeft, false);Skip buying on this day

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

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

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

Line Notes

function dfs(i, transactionsLeft, holding) {Recursive helper tracking day, transactions left, and holding

if (i === n || transactionsLeft === 0) return 0;Base case to end recursion

if (holding) {Branch when holding stock

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

const hold = dfs(i + 1, transactionsLeft, true);Option to hold stock without selling

const buy = -prices[i] + dfs(i + 1, transactionsLeft, true);Buy stock and change holding state

const skip = dfs(i + 1, transactionsLeft, false);Skip buying on this day

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

⏱

Complexity

TimeO(2^n) exponential due to exploring all buy/sell combinations

SpaceO(n) recursion stack depth

At each day, two choices (buy/sell or skip) lead to exponential growth in calls

💡 For n=10, this means over 1000 calls; for n=20, 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.

🧠

Memoization (Top-Down DP)

💡 Memoization caches results of recursive calls to avoid repeated work, drastically improving efficiency.

Intuition

Store results of subproblems defined by day, transactions left, and holding state to reuse instead of recomputing.

Algorithm

1. Create a 3D cache keyed by day, transactions left, and holding state.
2. Modify recursive function to check cache before computing.
3. If cached, return stored result.
4. Otherwise compute, store in cache, and return.

💡 Memoization turns exponential recursion into polynomial time by avoiding repeated calculations.

</>

Code

def maxProfit(k, prices):
    n = len(prices)
    from functools import lru_cache
    @lru_cache(None)
    def dfs(i, transactions_left, holding):
        if i == n or transactions_left == 0:
            return 0
        if holding:
            sell = prices[i] + dfs(i + 1, transactions_left - 1, False)
            hold = dfs(i + 1, transactions_left, True)
            return max(sell, hold)
        else:
            buy = -prices[i] + dfs(i + 1, transactions_left, True)
            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

@lru_cache(None)Caches results of dfs calls to avoid recomputation

def dfs(i, transactions_left, holding):Recursive function with memoization

if i == n or transactions_left == 0:Base case to stop recursion

if holding:Branch when holding stock to decide sell or hold

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

hold = dfs(i + 1, transactions_left, True)Hold stock without selling

return max(sell, hold)Return best profit when holding stock

else:Branch when not holding stock to decide buy or skip

buy = -prices[i] + dfs(i + 1, transactions_left, True)Buy stock and change holding state

skip = dfs(i + 1, transactions_left, False)Skip buying on this day

return max(buy, skip)Return best profit when not holding stock

return dfs(0, k, False)Start recursion with no stock held

import java.util.*;
public class Solution {
    private Integer[][][] memo;
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        memo = new Integer[n][k + 1][2];
        return dfs(prices, 0, k, 0);
    }
    private int dfs(int[] prices, int i, int transactionsLeft, int holding) {
        if (i == prices.length || transactionsLeft == 0) return 0;
        if (memo[i][transactionsLeft][holding] != null) return memo[i][transactionsLeft][holding];
        int result;
        if (holding == 1) {
            int sell = prices[i] + dfs(prices, i + 1, transactionsLeft - 1, 0);
            int hold = dfs(prices, i + 1, transactionsLeft, 1);
            result = Math.max(sell, hold);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, 1);
            int skip = dfs(prices, i + 1, transactionsLeft, 0);
            result = Math.max(buy, skip);
        }
        memo[i][transactionsLeft][holding] = result;
        return result;
    }
    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

private Integer[][][] memo;3D memo array to cache results by day, transactions left, and holding

if (i == prices.length || transactionsLeft == 0) return 0;Base case for recursion termination

if (memo[i][transactionsLeft][holding] != null) return memo[i][transactionsLeft][holding];Return cached result if available

if (holding == 1) {Branch when holding stock to decide sell or hold

int sell = prices[i] + dfs(prices, i + 1, transactionsLeft - 1, 0);Sell stock and reduce transactions

int hold = dfs(prices, i + 1, transactionsLeft, 1);Hold stock without selling

result = Math.max(sell, hold);Choose max profit when holding

} else {Branch when not holding stock to decide buy or skip

int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, 1);Buy stock and change holding state

int skip = dfs(prices, i + 1, transactionsLeft, 0);Skip buying on this day

result = Math.max(buy, skip);Choose max profit when not holding

memo[i][transactionsLeft][holding] = result;Store computed result in cache

return dfs(prices, 0, k, 0);Start recursion with no stock held

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

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

class Solution {
    vector<vector<vector<int>>> memo;
public:
    int dfs(const vector<int>& prices, int i, int transactionsLeft, int holding) {
        if (i == prices.size() || transactionsLeft == 0) return 0;
        if (memo[i][transactionsLeft][holding] != -1) return memo[i][transactionsLeft][holding];
        int result;
        if (holding == 1) {
            int sell = prices[i] + dfs(prices, i + 1, transactionsLeft - 1, 0);
            int hold = dfs(prices, i + 1, transactionsLeft, 1);
            result = max(sell, hold);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, 1);
            int skip = dfs(prices, i + 1, transactionsLeft, 0);
            result = max(buy, skip);
        }
        return memo[i][transactionsLeft][holding] = result;
    }
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        memo.assign(n, vector<vector<int>>(k + 1, vector<int>(2, -1)));
        return dfs(prices, 0, k, 0);
    }
};

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

Line Notes

vector<vector<vector<int>>> memo;3D vector for memoization cache

if (i == prices.size() || transactionsLeft == 0) return 0;Base case to stop recursion

if (memo[i][transactionsLeft][holding] != -1) return memo[i][transactionsLeft][holding];Return cached result if computed

if (holding == 1) {Branch when holding stock to decide sell or hold

int sell = prices[i] + dfs(prices, i + 1, transactionsLeft - 1, 0);Sell stock and reduce transactions

int hold = dfs(prices, i + 1, transactionsLeft, 1);Hold stock without selling

result = max(sell, hold);Choose max profit when holding

} else {Branch when not holding stock to decide buy or skip

int buy = -prices[i] + dfs(prices, i + 1, transactionsLeft, 1);Buy stock and change holding state

int skip = dfs(prices, i + 1, transactionsLeft, 0);Skip buying on this day

result = max(buy, skip);Choose max profit when not holding

return memo[i][transactionsLeft][holding] = result;Store and return computed result

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

function maxProfit(k, prices) {
    const n = prices.length;
    const memo = new Array(n).fill(0).map(() =>
        new Array(k + 1).fill(0).map(() => new Array(2).fill(null)));
    function dfs(i, transactionsLeft, holding) {
        if (i === n || transactionsLeft === 0) return 0;
        if (memo[i][transactionsLeft][holding] !== null) return memo[i][transactionsLeft][holding];
        let result;
        if (holding) {
            const sell = prices[i] + dfs(i + 1, transactionsLeft - 1, 0);
            const hold = dfs(i + 1, transactionsLeft, 1);
            result = Math.max(sell, hold);
        } else {
            const buy = -prices[i] + dfs(i + 1, transactionsLeft, 1);
            const skip = dfs(i + 1, transactionsLeft, 0);
            result = Math.max(buy, skip);
        }
        memo[i][transactionsLeft][holding] = result;
        return result;
    }
    return dfs(0, k, 0);
}

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

Line Notes

const memo = new Array(n).fill(0).map(() =>Initialize 3D memo array with nulls

if (i === n || transactionsLeft === 0) return 0;Base case to end recursion

if (memo[i][transactionsLeft][holding] !== null) return memo[i][transactionsLeft][holding];Return cached result if available

if (holding) {Branch when holding stock to decide sell or hold

const sell = prices[i] + dfs(i + 1, transactionsLeft - 1, 0);Sell stock and reduce transactions

const hold = dfs(i + 1, transactionsLeft, 1);Hold stock without selling

result = Math.max(sell, hold);Choose max profit when holding

} else {Branch when not holding stock to decide buy or skip

const buy = -prices[i] + dfs(i + 1, transactionsLeft, 1);Buy stock and change holding state

const skip = dfs(i + 1, transactionsLeft, 0);Skip buying on this day

result = Math.max(buy, skip);Choose max profit when not holding

memo[i][transactionsLeft][holding] = result;Cache computed result

return dfs(0, k, 0);Start recursion with no stock held

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

⏱

Complexity

TimeO(n * k * 2) = O(nk) due to memoization of states

SpaceO(n * k * 2) for memo cache and recursion stack

Each day, transaction count, and holding state combination is computed once

💡 For n=1000 and k=10, this means about 20,000 computations, which is feasible.

Interview Verdict: Accepted

Memoization makes the brute force approach efficient enough for large inputs.

🧠

Tabulation (Bottom-Up DP)

💡 Tabulation builds the solution iteratively from the base cases up, avoiding recursion and often improving clarity and performance.

Intuition

Use a 3D DP table indexed by day, transactions left, and holding state to iteratively compute max profit.

Algorithm

1. Initialize a 3D DP array dp[n+1][k+1][2] with zeros.
2. Iterate days from n-1 down to 0.
3. For each day, iterate transactions left from 1 to k.
4. Update dp based on whether holding or not, choosing max of buy/sell/skip/hold.
5. Return dp[0][k][0] as the answer.

💡 The bottom-up approach systematically fills the DP table using previously computed results.

</>

Code

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    dp = [[[0]*2 for _ in range(k+1)] for __ in range(n+1)]
    for i in range(n-1, -1, -1):
        for t in range(1, k+1):
            dp[i][t][0] = max(-prices[i] + dp[i+1][t][1], dp[i+1][t][0])
            dp[i][t][1] = max(prices[i] + dp[i+1][t-1][0], dp[i+1][t][1])
    return dp[0][k][0]

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

Line Notes

if k >= n // 2:Shortcut for unlimited transactions case

profit = 0Initialize profit accumulator

for i in range(1, n):Iterate over days to accumulate profit

profit += max(0, prices[i] - prices[i - 1])Add positive price differences for unlimited transactions

dp = [[[0]*2 for _ in range(k+1)] for __ in range(n+1)]Initialize 3D DP array with zeros

for i in range(n-1, -1, -1):Iterate days backwards

for t in range(1, k+1):Iterate over transaction counts

dp[i][t][0] = max(-prices[i] + dp[i+1][t][1], dp[i+1][t][0])Max profit if not holding: buy or skip

dp[i][t][1] = max(prices[i] + dp[i+1][t-1][0], dp[i+1][t][1])Max profit if holding: sell or hold

return dp[0][k][0]Return max profit starting at day 0 with k transactions and no stock held

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                profit += Math.max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }
        int[][][] dp = new int[n + 1][k + 1][2];
        for (int i = n - 1; i >= 0; i--) {
            for (int t = 1; t <= k; t++) {
                dp[i][t][0] = Math.max(-prices[i] + dp[i + 1][t][1], dp[i + 1][t][0]);
                dp[i][t][1] = Math.max(prices[i] + dp[i + 1][t - 1][0], dp[i + 1][t][1]);
            }
        }
        return dp[0][k][0];
    }
    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

if (k >= n / 2) {Handle unlimited transactions case efficiently

int profit = 0;Initialize profit accumulator

for (int i = 1; i < n; i++) {Iterate over days to accumulate profit

profit += Math.max(0, prices[i] - prices[i - 1]);Add positive price differences for unlimited transactions

int[][][] dp = new int[n + 1][k + 1][2];3D DP array for day, transactions left, holding

for (int i = n - 1; i >= 0; i--) {Iterate days backwards

for (int t = 1; t <= k; t++) {Iterate over transaction counts

dp[i][t][0] = Math.max(-prices[i] + dp[i + 1][t][1], dp[i + 1][t][0]);Buy or skip when not holding

dp[i][t][1] = Math.max(prices[i] + dp[i + 1][t - 1][0], dp[i + 1][t][1]);Sell or hold when holding

return dp[0][k][0];Return max profit starting at day 0 with k transactions and no stock held

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

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                profit += max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));
        for (int i = n - 1; i >= 0; i--) {
            for (int t = 1; t <= k; t++) {
                dp[i][t][0] = max(-prices[i] + dp[i + 1][t][1], dp[i + 1][t][0]);
                dp[i][t][1] = max(prices[i] + dp[i + 1][t - 1][0], dp[i + 1][t][1]);
            }
        }
        return dp[0][k][0];
    }
};

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

Line Notes

if (k >= n / 2) {Shortcut for unlimited transactions

int profit = 0;Initialize profit accumulator

for (int i = 1; i < n; i++) {Iterate over days to accumulate profit

profit += max(0, prices[i] - prices[i - 1]);Add positive price differences for unlimited transactions

vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));3D DP table initialization

for (int i = n - 1; i >= 0; i--) {Iterate days backwards

for (int t = 1; t <= k; t++) {Iterate over transaction counts

dp[i][t][0] = max(-prices[i] + dp[i + 1][t][1], dp[i + 1][t][0]);Buy or skip when not holding

dp[i][t][1] = max(prices[i] + dp[i + 1][t - 1][0], dp[i + 1][t][1]);Sell or hold when holding

return dp[0][k][0];Return max profit starting at day 0 with k transactions and no stock held

function maxProfit(k, prices) {
    const n = prices.length;
    if (k >= Math.floor(n / 2)) {
        let profit = 0;
        for (let i = 1; i < n; i++) {
            profit += Math.max(0, prices[i] - prices[i - 1]);
        }
        return profit;
    }
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: k + 1 }, () => [0, 0])
    );
    for (let i = n - 1; i >= 0; i--) {
        for (let t = 1; t <= k; t++) {
            dp[i][t][0] = Math.max(-prices[i] + dp[i + 1][t][1], dp[i + 1][t][0]);
            dp[i][t][1] = Math.max(prices[i] + dp[i + 1][t - 1][0], dp[i + 1][t][1]);
        }
    }
    return dp[0][k][0];
}

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

Line Notes

if (k >= Math.floor(n / 2)) {Handle unlimited transactions case

let profit = 0;Initialize profit accumulator

for (let i = 1; i < n; i++) {Iterate over days to accumulate profit

profit += Math.max(0, prices[i] - prices[i - 1]);Add positive price differences for unlimited transactions

const dp = Array.from({ length: n + 1 }, () =>Initialize 3D DP array

for (let i = n - 1; i >= 0; i--) {Iterate days backwards

for (let t = 1; t <= k; t++) {Iterate over transaction counts

dp[i][t][0] = Math.max(-prices[i] + dp[i + 1][t][1], dp[i + 1][t][0]);Buy or skip when not holding

dp[i][t][1] = Math.max(prices[i] + dp[i + 1][t - 1][0], dp[i + 1][t][1]);Sell or hold when holding

return dp[0][k][0];Return max profit starting at day 0 with k transactions and no stock held

⏱

Complexity

TimeO(nk)

SpaceO(nk)

We fill a DP table of size n*k*2 iteratively

💡 For n=1000 and k=10, about 20,000 operations, efficient for interviews.

Interview Verdict: Accepted

Tabulation is a clean and efficient way to solve this problem without recursion.

🧠

Space Optimized DP

💡 Since dp[i] depends only on dp[i+1], we can reduce space from O(nk) to O(k) by storing only next day states.

Intuition

Keep track of only the next day's dp states for each transaction count and holding state, updating in reverse order.

Algorithm

1. Initialize two 2D arrays for current and next day states with dimensions (k+1) x 2.
2. Iterate days backwards from n-1 to 0.
3. For each transaction count, update current day states using next day states.
4. Swap current and next day states after each day iteration.
5. Return the max profit from day 0 with k transactions and no stock held.

💡 This approach reduces memory by reusing arrays and only storing necessary states.

</>

Code

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

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

Line Notes

if k >= n // 2:Handle unlimited transactions case

profit = 0Initialize profit accumulator

for i in range(1, n):Iterate over days to accumulate profit

profit += max(0, prices[i] - prices[i - 1])Add positive price differences for unlimited transactions

next_dp = [[0, 0] for _ in range(k + 1)]Initialize next day DP states

curr_dp = [[0, 0] for _ in range(k + 1)]Initialize current day DP states

for i in range(n - 1, -1, -1):Iterate days backwards

for t in range(1, k + 1):Iterate over transaction counts

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])Buy or skip when not holding

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])Sell or hold when holding

next_dp, curr_dp = curr_dp, next_dpSwap current and next day states for next iteration

return next_dp[k][0]Return max profit starting at day 0 with k transactions and no stock held

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                profit += Math.max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }
        int[][] next_dp = new int[k + 1][2];
        int[][] curr_dp = new int[k + 1][2];
        for (int i = n - 1; i >= 0; i--) {
            for (int t = 1; t <= k; t++) {
                curr_dp[t][0] = Math.max(-prices[i] + next_dp[t][1], next_dp[t][0]);
                curr_dp[t][1] = Math.max(prices[i] + next_dp[t - 1][0], next_dp[t][1]);
            }
            int[][] temp = next_dp;
            next_dp = curr_dp;
            curr_dp = temp;
        }
        return next_dp[k][0];
    }
    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

if (k >= n / 2) {Handle unlimited transactions case

int profit = 0;Initialize profit accumulator

for (int i = 1; i < n; i++) {Iterate over days to accumulate profit

profit += Math.max(0, prices[i] - prices[i - 1]);Add positive price differences for unlimited transactions

int[][] next_dp = new int[k + 1][2];Next day DP states

int[][] curr_dp = new int[k + 1][2];Current day DP states

for (int i = n - 1; i >= 0; i--) {Iterate days backwards

for (int t = 1; t <= k; t++) {Iterate over transaction counts

curr_dp[t][0] = Math.max(-prices[i] + next_dp[t][1], next_dp[t][0]);Buy or skip when not holding

curr_dp[t][1] = Math.max(prices[i] + next_dp[t - 1][0], next_dp[t][1]);Sell or hold when holding

int[][] temp = next_dp; next_dp = curr_dp; curr_dp = temp;Swap references for next iteration

return next_dp[k][0];Return max profit starting at day 0 with k transactions and no stock held

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

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                profit += max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }
        vector<vector<int>> next_dp(k + 1, vector<int>(2, 0));
        vector<vector<int>> curr_dp(k + 1, vector<int>(2, 0));
        for (int i = n - 1; i >= 0; i--) {
            for (int t = 1; t <= k; t++) {
                curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0]);
                curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1]);
            }
            swap(next_dp, curr_dp);
        }
        return next_dp[k][0];
    }
};

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

Line Notes

if (k >= n / 2) {Handle unlimited transactions case

int profit = 0;Initialize profit accumulator

for (int i = 1; i < n; i++) {Iterate over days to accumulate profit

profit += max(0, prices[i] - prices[i - 1]);Add positive price differences for unlimited transactions

vector<vector<int>> next_dp(k + 1, vector<int>(2, 0));Next day DP states

vector<vector<int>> curr_dp(k + 1, vector<int>(2, 0));Current day DP states

for (int i = n - 1; i >= 0; i--) {Iterate days backwards

for (int t = 1; t <= k; t++) {Iterate over transaction counts

curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0]);Buy or skip when not holding

curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1]);Sell or hold when holding

swap(next_dp, curr_dp);Swap DP arrays for next iteration

return next_dp[k][0];Return max profit starting at day 0 with k transactions and no stock held

function maxProfit(k, prices) {
    const n = prices.length;
    if (k >= Math.floor(n / 2)) {
        let profit = 0;
        for (let i = 1; i < n; i++) {
            profit += Math.max(0, prices[i] - prices[i - 1]);
        }
        return profit;
    }
    let next_dp = Array.from({ length: k + 1 }, () => [0, 0]);
    let curr_dp = Array.from({ length: k + 1 }, () => [0, 0]);
    for (let i = n - 1; i >= 0; i--) {
        for (let t = 1; t <= k; t++) {
            curr_dp[t][0] = Math.max(-prices[i] + next_dp[t][1], next_dp[t][0]);
            curr_dp[t][1] = Math.max(prices[i] + next_dp[t - 1][0], next_dp[t][1]);
        }
        [next_dp, curr_dp] = [curr_dp, next_dp];
    }
    return next_dp[k][0];
}

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

Line Notes

if (k >= Math.floor(n / 2)) {Handle unlimited transactions case

let profit = 0;Initialize profit accumulator

for (let i = 1; i < n; i++) {Iterate over days to accumulate profit

profit += Math.max(0, prices[i] - prices[i - 1]);Add positive price differences for unlimited transactions

let next_dp = Array.from({ length: k + 1 }, () => [0, 0]);Next day DP states

let curr_dp = Array.from({ length: k + 1 }, () => [0, 0]);Current day DP states

for (let i = n - 1; i >= 0; i--) {Iterate days backwards

for (let t = 1; t <= k; t++) {Iterate over transaction counts

curr_dp[t][0] = Math.max(-prices[i] + next_dp[t][1], next_dp[t][0]);Buy or skip when not holding

curr_dp[t][1] = Math.max(prices[i] + next_dp[t - 1][0], next_dp[t][1]);Sell or hold when holding

[next_dp, curr_dp] = [curr_dp, next_dp];Swap DP arrays for next iteration

return next_dp[k][0];Return max profit starting at day 0 with k transactions and no stock held

⏱

Complexity

TimeO(nk)

SpaceO(k)

Only two arrays of size k are maintained, reducing space from O(nk) to O(k)

💡 For k=10, this reduces memory usage drastically while keeping time efficient.

Interview Verdict: Accepted

Space optimization is a practical improvement for large inputs and is a good interview talking point.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation are best to code in interviews; brute force is for explanation only.

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. Memoization	O(nk)	O(nk)	Possible but less likely	Yes	Good for explaining optimization
3. Tabulation	O(nk)	O(nk)	No	Yes	Preferred for coding
4. Space Optimized DP	O(nk)	O(k)	No	Yes, with extra bookkeeping	Mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice explaining each approach clearly before interviews.

How to Present

Clarify problem constraints and ask about edge cases.Explain brute force recursion to show understanding of problem structure.Introduce memoization to optimize recursion with caching.Present bottom-up tabulation as an iterative alternative.Mention space optimization to reduce memory usage.Code the most optimal approach you are comfortable with.Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 7min → Code: 15min → Test: 5min. Total ~30min

What the Interviewer Tests

Ability to identify overlapping subproblems, optimize recursion, handle edge cases, and write clean DP code.

Common Follow-ups

• What if k is very large? → Use unlimited transactions shortcut.
• Can you optimize space? → Use space optimized DP with two arrays.

💡 These follow-ups test your understanding of problem constraints and ability to optimize further.

🔍

Pattern Recognition

When to Use

1) Problem involves stock buy/sell with transaction limits, 2) Maximize profit, 3) State depends on day, transactions left, and holding, 4) Overlapping subproblems exist

Signature Phrases

at most k transactionsmaximize profitbuy and sell stock

NOT This Pattern When

Problems without transaction limits or with cooldowns/different constraints are different patterns.

Similar Problems

Best Time to Buy and Sell Stock I - single transactionBest Time to Buy and Sell Stock II - unlimited transactionsBest Time to Buy and Sell Stock III - at most two transactions

Practice

1. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

2. Given the following code snippet implementing the two-pointer approach for trapping rain water, what is the value of the variable water after the first iteration of the while loop when the input is [2, 0, 2]?

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: First iteration of while loop

   height[left]=2, height[right]=2, since height[left] is not less than height[right], else branch runs. height[right]=2 ≥ right_max=0, so right_max=2, right decrements to 1, water remains 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Water not added on first iteration because max updated [OK]

Hint: Water added only when current height < max height on that side [OK]

Common Mistakes:

• Adding water before max height is updated
• Confusing left and right pointer conditions
• Off-by-one errors in pointer movement

3. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n (number of balloons)?

medium

A. O(n * 2^n)

B. O(n^2)

C. O(n^3)

D. O(n^4)

Solution

1. Step 1: Identify nested loops in the bottom-up DP

   There are three nested loops: length (up to n), left (up to n), and i (between left and right), each up to n.

2. Step 2: Calculate total operations

   Multiplying the three loops gives O(n^3) time complexity. The dp table is size n^2, so space is O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Three nested loops over n -> O(n^3) [OK]

Hint: Three nested loops over n cause cubic time [OK]

Common Mistakes:

• Confusing with exponential brute force
• Forgetting the third loop
• Assuming quadratic time

4. The following code snippet is a near-correct implementation of the Trie-based palindrome pairs solution. Which line contains a subtle bug that causes incorrect results on inputs containing empty strings?

medium

A. Line missing palindrome_suffixes append after setting node.index

B. Line checking is_palindrome(word[:len(word)-i]) inside add_word loop

C. Line checking is_palindrome(word[i:]) inside search loop

D. Line returning res when ch not in node.children

Solution

1. Step 1: Identify missing palindrome suffix append

   After setting node.index, the code must append index to palindrome_suffixes to handle empty string cases correctly.

2. Step 2: Understand impact on empty string pairs

   Without this append, pairs involving empty strings and palindromic words are missed, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding palindrome_suffixes append fixes empty string pairing [OK]

Hint: Empty string pairs require palindrome_suffixes append at word end [OK]

Common Mistakes:

• Forgetting to append palindrome_suffixes at word end
• Misplacing palindrome checks
• Incorrect early returns in search

5. Consider the following buggy implementation of the two-pointer approach for trapping rain water. Which line contains the subtle bug that can cause incorrect trapped water calculation?

medium

A. Line 7: if height[left] < height[right]:

B. Line 15: if height[right] >= right_max:

C. Line 17: water += right_max - height[right]

D. Line 9: if height[left] > left_max:

Solution

1. Step 1: Compare condition for updating left_max

   The original buggy code used '>' instead of '>=' which causes left_max not to update when height[left] equals left_max.

2. Step 2: Effect of bug

   When height[left] == left_max, water is incorrectly added (left_max - height[left] = 0), which is harmless but logically incorrect and can cause issues in some cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using '>=' ensures correct max update and prevents unnecessary water addition [OK]

Hint: Use '>=' when updating max heights to avoid underestimation [OK]

Common Mistakes:

• Using '>' instead of '>=' for max updates
• Incorrect pointer movement
• Adding water without checking max heights