Best Time - Unlimited Transactions

📋

Problem

Imagine you are a stock trader who can buy and sell a stock any number of times to maximize profit. How do you decide when to buy and sell to get the best total profit?

Given an array prices where prices[i] is the price of a given stock on the i-th day, find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). However, you must sell the stock before you buy again.

1 ≤ prices.length ≤ 10^50 ≤ prices[i] ≤ 10^4

Edge cases: prices with all equal values → expected output 0prices with strictly decreasing values → expected output 0prices with strictly increasing values → expected output prices[n-1] - prices[0]

</>

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 logic to sum positive price differences.✅ Implement summation of all positive differences between consecutive prices.

Wrong: prices[n-1] - prices[0]Assuming only one transaction allowed instead of unlimited transactions.✅ Sum all positive consecutive price differences instead of single max difference.

Wrong: Non-zero on empty or single-element inputNot handling base cases properly, causing index errors or incorrect returns.✅ Add checks for empty or single-element prices and return 0 immediately.

Wrong: Positive profit on strictly decreasing pricesSumming all differences instead of only positive ones.✅ Sum only positive differences between consecutive days.

Wrong: TLE or timeoutUsing brute force exponential recursion instead of O(n) DP or greedy.✅ Implement O(n) time solution by summing positive differences or using DP.

✓

Test Cases

Try testing your code on empty and single-element arrays to handle base cases.

Consider tricky price sequences that might fool greedy or single-transaction logic.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

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

Expected7

⏱ Performance - must finish in 2000ms

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

💡 Consider all pairs of days where selling price is higher than buying price.

💡 Use dynamic programming or state machine to track holding and not holding states.

💡 Sum all positive differences between consecutive days' prices.

Why it failed: Incorrect profit indicates missing some profitable transactions. Fix by summing all positive price differences between consecutive days.

✓ Correctly sums all profitable transactions.

t1_02basic

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

Expected4

⏱ Performance - must finish in 2000ms

Prices strictly increase each day; buy on day 1 and sell on day 5 for profit 4.

💡 Check if summing all positive consecutive differences matches the max profit.

💡 This is a classic unlimited transactions scenario.

💡 Profit equals last price minus first price when prices strictly increase.

Why it failed: Failing this test means not capturing all incremental profits or treating as single transaction only. Fix by summing all positive consecutive differences.

✓ Correctly handles strictly increasing prices by summing all increments.

t2_01edge

Input{"prices":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty price list means no transactions possible, profit is 0.

💡 Consider what happens when prices array is empty.

💡 No days means no buy or sell actions.

💡 Return 0 immediately if prices is empty.

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

✓ Handles empty input gracefully with zero profit.

t2_02edge

Input{"prices":[5]}

Expected0

⏱ Performance - must finish in 2000ms

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

💡 With only one price, no transactions can be completed.

💡 Check if code handles single-element arrays correctly.

💡 Return 0 if prices length is 1.

Why it failed: Code returns non-zero profit for single day input. Fix by ensuring no transaction occurs if only one price.

✓ Correctly returns zero profit for single day input.

t2_03edge

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

Expected0

⏱ Performance - must finish in 2000ms

All prices equal means no profitable transactions, profit is 0.

💡 Check if code sums only positive price differences.

💡 No positive differences exist if all prices are equal.

💡 Profit should be zero when no price increase occurs.

Why it failed: Code returns positive profit when prices are constant. Fix by summing only positive differences.

✓ Correctly returns zero profit for constant prices.

t3_01corner

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

Expected0

⏱ Performance - must finish in 2000ms

Strictly decreasing prices mean no profitable transactions, profit is 0.

💡 Check if code avoids buying when prices are falling.

💡 No positive price differences exist in strictly decreasing sequence.

💡 Profit should be zero when no price increase occurs.

Why it failed: Code returns positive profit on decreasing prices. Fix by summing only positive differences between consecutive days.

✓ Correctly returns zero profit for strictly decreasing prices.

t3_02corner

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

Expected8

⏱ Performance - must finish in 2000ms

Multiple ups and downs: buy low and sell high multiple times for total profit 7.

💡 Greedy approach may fail if it misses some profitable transactions.

💡 Use DP or sum all positive consecutive differences to capture all profits.

💡 Sum (2-1)+(3-2)+(3-2)+(4-3)+(5-1) carefully to get total profit.

Why it failed: Greedy approach that only picks local maxima once misses some profits. Fix by summing all positive consecutive differences.

✓ Correctly handles multiple transactions with ups and downs.

t3_03corner

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

Expected14

⏱ Performance - must finish in 2000ms

Buy early and sell at peak, then buy at zero and sell at 10 for total profit 14.

💡 Check if code handles multiple buy/sell cycles correctly.

💡 Avoid confusion between 0/1 transaction limit and unlimited transactions.

💡 Sum positive differences: (2-1)+(3-2)+(4-3)+(5-4)+(10-0).

Why it failed: Code treating problem as single transaction returns 9 instead of 14. Fix by allowing unlimited transactions and summing all positive differences.

✓ Correctly sums profits over multiple buy/sell cycles.

t4_01performance

Input{"prices":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901]}

Expected0

⏱ Performance - must finish in 2000ms

n=100 strictly decreasing prices, O(n) solution must complete within 2 seconds.

💡 Use O(n) time dynamic programming or greedy summation.

💡 Avoid exponential brute force recursion.

💡 Sum only positive differences; here none exist, so profit is zero.

Why it failed: Brute force or exponential solutions time out on large input. Fix by implementing O(n) DP or greedy approach.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following buggy code snippet for maxProfit. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line with 'if k >= n // 2:' condition

B. Line with 'for j in range(1, k + 1):' loop iterating forwards

C. Line initializing buy array with -float('inf')

D. Line returning sell[k] at the end

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates forwards from 1 to k, which causes buy[j] to use updated sell[j-1] from the same iteration, corrupting state.

2. Step 2: Correct iteration order

   Iterating backwards from k down to 1 prevents premature overwriting of states, preserving correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Forward iteration overwrites dp states too early [OK]

Hint: Inner loop must run backwards to avoid state overwrite [OK]

Common Mistakes:

• Forgetting to iterate backwards in space optimized DP

2. The following code attempts to count the number of ways to decode a string. Which line contains a subtle bug that causes incorrect results for inputs containing '0'?

medium

A. if s[i] != '0':

B. curr += prev1 # inside two_digit check

C. if 10 <= two_digit <= 26:

D. prev2, prev1 = prev1, curr

Solution

1. Step 1: Identify two-digit addition logic

   The two-digit check should add prev2, not prev1, because it represents ways two steps back.

2. Step 2: Understand impact on '0' handling

   Adding prev1 instead of prev2 causes overcounting or invalid counts when '0' appears, e.g., '10' or '20'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct two-digit addition uses prev2, not prev1 [OK]

Hint: Two-digit addition must add prev2, not prev1 [OK]

Common Mistakes:

• Confusing prev1 and prev2 in two-digit addition

3. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why?

medium

A. O(n) because it iterates through the array once updating maxReach

B. O(n^2) because each position may check multiple jumps

C. O(n log n) due to sorting or priority queue operations

D. O(2^n) because of exploring all jump paths recursively

Solution

1. Step 1: Identify loop structure

   The greedy solution iterates through the array once, updating maxReach in O(1) time per iteration.

2. Step 2: Confirm no nested loops or recursion

   There are no nested loops or recursion, so total time is linear in array length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass over array -> O(n) time [OK]

Hint: Greedy uses single pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming sorting is needed
• Forgetting recursion stack space

4. What is the time complexity of the optimal bottom-up DP solution for the Word Break problem, where n is the length of the input string, m is the number of unique word lengths in the dictionary, and k is the maximum word length?

medium

A. O(n * m * k) because for each position we check only word lengths and substring membership

B. O(2^n) due to exploring all segmentations recursively

C. O(n * m) because substring extraction is O(1) and membership check is O(1)

D. O(n^2) because for each index we check all previous indices

Solution

1. Step 1: Identify loops and operations

   The outer loop runs n times. For each i, inner loop runs over m unique word lengths. Substring extraction takes O(k) time, and membership check in a set is O(1).

2. Step 2: Combine to get total complexity

   Total time is O(n * m * k). The naive O(n^2) is incorrect because we don't check all previous indices, only those corresponding to word lengths.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Loops over n and m, substring extraction O(k) -> O(n*m*k) [OK]

Hint: Check loops and substring extraction cost carefully [OK]

Common Mistakes:

• Assuming O(n^2) by checking all indices
• Ignoring substring extraction cost
• Confusing recursive exponential with DP complexity

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Change dp array to store counts of ways to segment instead of booleans

B. No change needed; the original DP already supports unlimited reuse of words

C. Remove the break statement after setting dp[i] = True to consider all segmentations

D. Use a recursive backtracking approach without memoization to explore all reuse possibilities

Solution

1. Step 1: Understand the reuse requirement

   Unlimited reuse means counting all possible segmentations, not just checking existence.

2. Step 2: Modify DP to count ways

   Change dp from boolean to integer counts, summing counts from dp[i - length] when substring is in dictionary.

3. Step 3: Evaluate other options

   Original DP only checks existence (boolean), removing break doesn't count ways correctly, recursion without memoization is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting ways requires dp to store counts, not booleans [OK]

Hint: Counting segmentations requires dp to store counts, not booleans [OK]

Common Mistakes:

• Assuming original DP counts ways
• Removing break to count ways incorrectly
• Using naive recursion without memoization