Best Time to Buy and Sell Stock (1 tx)

📋

Problem

Imagine you are an investor who wants to maximize profit by buying and selling a single stock once over a period of days. You want to know the best day to buy and the best day to sell to maximize your gain.

Given an array prices where prices[i] is the price of a given stock on the ith day, find the maximum profit you can achieve by making at most one transaction (i.e., buy one and sell one share of the stock). If no profit can be made, return 0.

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

Edge cases: Only one day → output 0 (cannot sell)Prices are all the same → output 0 (no profit)Prices strictly decreasing → output 0 (no profit)

</>

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: 0Always returning 0 without checking for profitable transactions.✅ Track min_price and update max_profit = max(max_profit, current_price - min_price) during iteration.

Wrong: profit from local max instead of global maxGreedy approach that sells at first local maximum instead of global maximum.✅ Do not sell immediately; track min_price globally and update max_profit at each step.

Wrong: positive profit on strictly decreasing pricesNot checking if current price is less than min_price before updating profit.✅ Update min_price when current price is lower; only update max_profit if current price - min_price > max_profit.

Wrong: TLE on large inputUsing O(n^2) brute force nested loops approach.✅ Implement O(n) single pass solution tracking min_price and max_profit.

✓

Test Cases

Focus on handling minimal input sizes and no profit scenarios correctly.

Test your solution against tricky sequences that can fool greedy approaches.

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

t1_01basic

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

Expected5

⏱ Performance - must finish in 2000ms

Buy on day 2 (price=1) and sell on day 5 (price=6), profit = 6-1 = 5.

💡 Track the minimum price seen so far and calculate profit if sold today.

💡 Use a single pass to update max profit by comparing current price with min price.

💡 Update min price when a lower price is found; max profit is max of previous max and current price - min price.

Why it failed: Returned incorrect profit; likely did not track minimum price correctly or did not update max profit properly. Fix by maintaining min_price and updating max_profit = max(max_profit, current_price - min_price).

✓ Correctly computes max profit using single pass tracking minimum price.

t1_02basic

Input{"prices":[3,8,6,7,6,9,2]}

Expected6

⏱ Performance - must finish in 2000ms

Buy on day 1 (price=3) and sell on day 2 (price=8), profit = 8-3 = 5; better to buy on day 7 (price=2) and sell on day 6 (price=9) is invalid since sell must be after buy; best is buy day 1 sell day 6 profit 9-3=6.

💡 Remember you must buy before you sell; track min price and max profit.

💡 Check all days updating min price and max profit accordingly.

💡 Max profit is max of previous max and current price minus min price.

Why it failed: Incorrect profit due to not enforcing buy before sell or not updating min price correctly. Fix by ensuring min_price is updated only when a lower price is found and max_profit updated as max(max_profit, current_price - min_price).

✓ Correctly handles multiple ups and downs to find max profit.

t2_01edge

Input{"prices":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Only one day, cannot sell after buying, so profit is 0.

💡 Check if array length is less than 2, profit must be 0.

💡 No valid sell day after buy day if only one price.

💡 Return 0 when prices length is 1 or less.

Why it failed: Returned non-zero profit for single day input; fix by returning 0 if prices length < 2.

✓ Correctly returns 0 for single day input.

t2_02edge

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

Expected0

⏱ Performance - must finish in 2000ms

All prices are the same, no profit possible, so output is 0.

💡 Check if prices never increase over time.

💡 Max profit is zero if no price is greater than min price.

💡 Return 0 if max profit remains zero after processing all prices.

Why it failed: Returned positive profit when prices are constant; fix by ensuring max_profit only updates if current price > min_price.

✓ Correctly returns 0 when no profit is possible.

t2_03edge

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

Expected0

⏱ Performance - must finish in 2000ms

Prices strictly decreasing, no profit possible, so output is 0.

💡 Track min price and max profit; max profit should remain 0 if prices decrease.

💡 No day to sell at higher price than buy day.

💡 Return 0 if max profit never increases.

Why it failed: Returned positive profit for strictly decreasing prices; fix by updating max_profit only if current price - min_price > max_profit.

✓ Correctly returns 0 for strictly decreasing prices.

t3_01corner

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

Expected4

⏱ Performance - must finish in 2000ms

Prices strictly increasing, best to buy on day 1 and sell on last day, profit = 5-1 = 4.

💡 Check if your solution handles strictly increasing sequences correctly.

💡 Max profit should be last price minus first price in increasing array.

💡 Ensure min_price is updated only when lower price found and max_profit updated accordingly.

Why it failed: Incorrect profit due to greedy approach that sells too early or off-by-one error; fix by tracking min_price and updating max_profit at each step.

✓ Correctly handles strictly increasing prices for max profit.

t3_02corner

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

Expected4

⏱ Performance - must finish in 2000ms

Buy on day 2 (price=2) and sell on day 3 (price=6), profit = 4; buying on day 4 (price=1) and selling on day 5 (price=4) yields profit 3, less than 4.

💡 Beware of greedy mistakes that pick local max instead of global max profit.

💡 Track min price and update max profit at each day.

💡 Do not reset min price incorrectly after a profit calculation.

Why it failed: Returned 3 instead of 4 due to greedy approach picking first local max; fix by always tracking global min price and updating max profit accordingly.

✓ Correctly finds global max profit despite local fluctuations.

t3_03corner

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

Expected7

⏱ Performance - must finish in 2000ms

Buy on day 2 (price=1) and sell on day 7 (price=8), profit = 7.

💡 Check if your solution considers all days after min price for selling.

💡 Do not stop updating max profit after first max found.

💡 Update max profit at every step comparing current price and min price.

Why it failed: Returned 5 instead of 7 due to stopping early or not updating max profit after initial max; fix by continuing to update max profit throughout iteration.

✓ Correctly finds max profit by considering all sell days after min price.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) solution to complete within 2 seconds.

💡 Brute force O(n^2) will time out; use O(n) single pass approach.

💡 Track minimum price and maximum profit in one pass.

💡 Avoid nested loops; update min price and max profit as you iterate.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing O(n) single pass solution tracking min price and max profit.

✓ Solution runs in O(n) time and completes within time limit.

Practice

1. You are given a list of daily stock prices and want to maximize profit by buying and selling stocks with the constraint that after selling a stock, you must wait one day before buying again. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Brute force recursion exploring all buy/sell/cooldown sequences without memoization

B. A greedy algorithm that buys at every local minimum and sells at every local maximum

C. Dynamic programming with state machine to track holding, cooldown, and free states

D. Divide and conquer splitting the price array into subproblems and merging results

Solution

1. Step 1: Understand the cooldown constraint

   The cooldown day after selling prevents immediate rebuying, which breaks greedy local min/max approaches.

2. Step 2: Recognize the need for state tracking

   Dynamic programming with states (holding, cooldown, free) models the problem accurately and efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy fails on cooldown; DP state machine handles it correctly [OK]

Hint: Cooldown requires state tracking, not greedy [OK]

Common Mistakes:

• Assuming greedy local min/max works despite cooldown
• Ignoring cooldown day after selling

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

Solution

1. Step 1: Analyze base case condition

   The condition 'if n < 1' returns 1 only when n is 0 or negative, but for n=1 it skips and runs the loop, which is incorrect.

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

   This ensures for n=0 or n=1, the function returns 1 immediately, matching problem definition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Base case off-by-one causes wrong results for n=1 [OK]

Hint: Check base cases carefully for off-by-one errors [OK]

Common Mistakes:

• Using '<' instead of '<=' in base cases
• Incorrect loop start index

3. Consider the following buggy code for Jump Game II. Which line contains the subtle bug that causes incorrect results for input arrays of length 1?

medium

A. Line 2: n = len(nums)

B. Line 9: return jumps

C. Line 3: jumps = 0

D. Line 5: for i in range(n - 1):

Solution

1. Step 1: Analyze loop range for single-element array

   When n=1, range(n-1) = range(0), so the loop does not run, and jumps remains 0.

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

   For an array of length 1, minimum jumps should be 0 (already at last index). The code returns 0, which is correct. However, if the problem expects at least one jump or code elsewhere assumes the loop runs, this can cause issues. The subtle bug is that the loop does not run for n=1, so no updates happen. If code elsewhere expects jumps increment, this is a problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop skipping for n=1 causes edge case bugs [OK]

Hint: Loop range excludes last index, skip for single-element arrays [OK]

Common Mistakes:

• Not handling single-element arrays properly
• Assuming loop always runs at least once
• Returning jumps without base case check

4. What is the time complexity of the optimal bottom-up dynamic programming solution for the minimum cost climbing stairs problem, and why?

medium

A. O(n) because each step computes cost using only two previous states

B. O(n²) because each step depends on all previous steps

C. O(2^n) due to exponential recursion calls

D. O(n log n) because of sorting costs before processing

Solution

1. Step 1: Analyze loop structure

   The bottom-up DP iterates once through the cost array of length n.

2. Step 2: Check dependencies per iteration

   Each iteration computes current cost using only two previous values, constant time per iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) work per step -> O(n) total [OK]

Hint: DP uses constant work per step, linear total time [OK]

Common Mistakes:

• Assuming quadratic due to nested loops
• Confusing recursion with DP iteration
• Thinking sorting is involved

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