Best Time to Buy Sell IV (K Transactions)

📋

Best Time to Buy Sell IV (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: 0Returning zero profit for all inputs due to missing DP logic or always returning base case.✅ Implement DP recurrence and avoid returning 0 prematurely except for base cases.

Wrong: Incorrect profit when k=0 or prices emptyMissing base case checks for k=0 or empty prices array.✅ Add if k==0 or prices empty: return 0 at start.

Wrong: Profit too high due to greedy summing multiple transactions when k=1Greedy approach ignoring transaction limit.✅ Limit transactions count and use DP to track states.

Wrong: TLE on large inputsUsing brute force recursion instead of DP.✅ Implement O(nk) DP or unlimited transactions shortcut.

Wrong: Incorrect profit when k >= n/2Not using unlimited transactions optimization.✅ Add shortcut: if k >= n/2, sum all positive price differences.

✓

Test Cases

Focus on handling base cases and empty inputs correctly.

Consider tricky cases that break greedy or naive DP approaches.

Optimize your DP to handle large inputs efficiently.

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.

💡 Think about tracking buy/sell states with at most k transactions.

💡 Use dynamic programming with states: day, transactions left, holding or not.

💡 Implement dp[i][t][holding] with recurrence considering buy, sell, or skip.

Why it failed: Incorrect profit means DP state transitions are wrong; ensure you decrement transactions only on sell and handle holding state properly.

✓ Correctly handles multiple transactions with DP state transitions.

t1_02basic

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

Expected4

⏱ Performance - must finish in 2000ms

With k=3, best is to buy day 1 and sell day 5 for profit 4; multiple transactions not needed.

💡 Check if k is large enough to allow unlimited transactions.

💡 If k >= n/2, sum all positive price differences.

💡 Sum (prices[i+1] - prices[i]) for all i where prices[i+1] > prices[i].

Why it failed: Failing to optimize for large k leads to TLE or wrong profit; add unlimited transactions shortcut when k >= n/2.

✓ Handles unlimited transactions case correctly.

t2_01edge

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

Expected0

⏱ Performance - must finish in 2000ms

No transactions allowed, so profit is zero regardless of prices.

💡 If k=0, no transactions can be made.

💡 Return 0 immediately when k=0.

💡 Add base case: if k == 0, return 0 without further processing.

Why it failed: Returning non-zero profit when k=0 means missing base case; fix by adding if k==0: return 0.

✓ Correctly returns zero profit when no transactions allowed.

t2_02edge

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

Expected0

⏱ Performance - must finish in 2000ms

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

💡 Check for empty prices array at start.

💡 Return 0 if prices is empty.

💡 Add base case: if not prices: return 0.

Why it failed: Code crashes or returns wrong value on empty input; add check for empty prices and return 0.

✓ Handles empty prices array gracefully with zero profit.

t2_03edge

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

Expected0

⏱ Performance - must finish in 2000ms

All prices equal, no profitable transactions possible, profit is zero.

💡 If prices never increase, profit is zero.

💡 Check that your DP does not add negative profits.

💡 Ensure max profit is never less than zero.

Why it failed: Returning negative or positive profit on flat prices means incorrect profit calculation; fix by ensuring profit >= 0.

✓ Correctly returns zero profit when no price increase.

t2_04edge

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

Expected0

⏱ Performance - must finish in 2000ms

Single day price means no opportunity to sell, profit is zero.

💡 With only one price, no transactions possible.

💡 Return 0 if prices length is 1.

💡 Add base case: if len(prices) < 2: return 0.

Why it failed: Returning non-zero profit on single price means missing base case; fix by checking prices length.

✓ Correctly returns zero profit for single price input.

t3_01corner

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

Expected8

⏱ Performance - must finish in 2000ms

With one transaction, best buy day 1 (price=1) and sell day 9 (price=9), profit=8.

💡 Greedy approach might pick multiple small profits incorrectly.

💡 DP must consider only one transaction max.

💡 Track max profit for single transaction by comparing min price so far.

Why it failed: Greedy summing multiple profits fails single transaction constraint; fix by limiting transactions to one and tracking min price.

✓ Correctly limits to one transaction profit.

t3_02corner

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

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Check if k >= n/2 to switch to unlimited transactions approach.

💡 Sum all positive price differences for unlimited transactions.

💡 Avoid DP when k is large to prevent TLE.

Why it failed: Treating large k as limited causes TLE or wrong profit; fix by adding unlimited transactions shortcut when k >= n/2.

✓ Handles large k with unlimited transactions optimization.

t3_03corner

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

Expected12

⏱ Performance - must finish in 2000ms

Best two transactions: buy day 2 sell day 3 (profit 4), buy day 5 sell day 7 (profit 7), total 11 originally stated but correct total profit is 10.

💡 Watch for off-by-one errors in indexing days.

💡 Ensure transactions count decrements only on sell.

💡 Verify DP state transitions handle all days correctly.

Why it failed: Off-by-one errors cause incorrect profit or index errors; fix indexing and transaction decrement logic.

✓ Correctly handles indexing and transaction counts.

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]}

Expected0

⏱ Performance - must finish in 2000ms

n=100, k=50; O(nk) DP must complete within 2 seconds.

💡 Use DP with O(nk) time complexity.

💡 Avoid exponential brute force recursion.

💡 Optimize space to O(k) if possible.

Why it failed: Brute force or exponential solutions TLE on large n and k; fix by implementing O(nk) DP.

✓ Efficient DP solution runs within time limit.

Practice

1. Consider the following Python code implementing the bidirectional BFS with state compression to find the shortest path visiting all nodes. Given the input graph = [[1,2,3],[0],[0],[0]], what is the final returned shortest path length?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Initialize queues and visited states

   For n=4 nodes, all_visited=15 (binary 1111). Each node starts in q1 with mask having only that node visited, and in q2 with mask having all nodes except that node visited.

2. Step 2: Trace BFS expansions

   From q1, starting at each node, BFS explores neighbors updating visited masks. The shortest path visiting all nodes in this star graph is 3 edges (e.g., 1->0->2->3).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Star graph shortest path length visiting all nodes is 3 edges [OK]

Hint: Star graph shortest path visiting all nodes equals 3 edges [OK]

Common Mistakes:

• Confusing number of nodes with number of edges in path
• Off-by-one errors in BFS distance counting
• Misinterpreting bitmask updates

2. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach that always picks the smallest current element and expands the range until all lists are covered.

B. Merge all lists into one sorted array with list indices, then use a two-pointer sliding window to find the minimal range covering all lists.

C. Apply dynamic programming to track the minimal range for subsets of lists incrementally.

D. Enumerate all possible combinations of elements from each list and select the combination with the smallest range.

Solution

1. Step 1: Understand problem constraints

   The problem requires a range covering at least one element from each list, which suggests tracking coverage across lists.

2. Step 2: Evaluate approaches

   Greedy alone fails because it doesn't guarantee minimal range; DP is not suitable due to combinatorial explosion; brute force enumerates all combos but is inefficient. Merging all lists and using two pointers efficiently tracks coverage and minimal range.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer on merged array is known optimal [OK]

Hint: Two pointers on merged array track coverage efficiently [OK]

Common Mistakes:

• Thinking greedy alone suffices
• Assuming DP applies directly
• Using brute force for large inputs

3. Examine the following buggy code snippet for the optimized trie approach. Which line contains the subtle bug that can cause incorrect results or runtime errors when no elements in nums are less than or equal to m in a query?

class TrieNode:
    def __init__(self):
        self.children = [null, null]

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def maxXor(self, num):
        node = self.root
        # Bug: missing check for empty trie
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if node.children[toggled_bit]:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

# rest of code omitted for brevity

medium

A. Line missing check if trie is empty before traversal in maxXor

B. Line 'if not node.children[bit]: node.children[bit] = TrieNode()' in insert method

C. Line with 'node = self.root' in maxXor method

D. Line 'node = node.children[bit]' in else branch of maxXor

Solution

1. Step 1: Identify missing empty trie check

   maxXor should return -1 if trie is empty (no children at root), but this check is missing.

2. Step 2: Consequence of missing check

   Without this, traversal accesses null children causing runtime error or incorrect results when no nums ≤ m.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 'if not node.children[0] and not node.children[1]: return -1' fixes bug [OK]

Hint: Always check if trie is empty before querying [OK]

Common Mistakes:

• Forgetting empty trie check
• Incorrect bit indexing
• Misplaced node updates

4. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the window must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts but ignore decrementing counts when shrinking window

B. Sort s and t and use two pointers to find minimal substring containing all chars

C. Use the original frequency counting approach but reset counts after each valid window

D. Use a set to track which characters from t are present in the window, and shrink when all are present

Solution

1. Step 1: Understand the variant

   Since counts do not matter and characters can be reused unlimited times, we only need to check presence of each unique character from t in the window.

2. Step 2: Modify tracking data structure

   Using a set to track which characters from t are currently in the window is sufficient. When the set contains all unique chars, the window is valid.

3. Step 3: Shrink window accordingly

   Shrink the window while maintaining presence of all required characters in the set.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking presence with a set fits the reuse variant [OK]

Hint: Presence tracking with set suffices when counts don't matter [OK]

Common Mistakes:

• Continuing to track exact counts unnecessarily
• Resetting counts incorrectly
• Sorting strings which breaks substring property

5. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column conflicts are ignored), but diagonal conflicts still apply. Which modification to the bitmask backtracking algorithm correctly adapts to this variant?

hard

A. Use a greedy approach placing queens row-wise ignoring conflicts

B. Remove the column bitmask cols from the pruning condition and keep diagonal bitmasks unchanged

C. Remove diagonal bitmasks and only use column bitmask to prune

D. Keep all bitmasks unchanged but allow multiple queens per column by skipping column checks

Solution

1. Step 1: Identify which constraints remain

   Column conflicts are ignored, so cols bitmask should not prune positions.

2. Step 2: Modify pruning condition

   Remove cols from available_positions = mask & ~(cols | pos_diags | neg_diags), keeping diagonal bitmasks to prune invalid diagonals.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Removing column mask allows multiple queens per column [OK]

Hint: Remove column mask to allow multiple queens per column [OK]

Common Mistakes:

• Removing diagonal masks breaks diagonal checks
• Ignoring pruning leads to exponential blowup
• Using greedy approach fails correctness