PPractick

The problem

A trading app offers a "perfect hindsight" feature: given a stock's daily prices, show the maximum profit from one buy followed by one later sell. If prices only fall, the best choice is not to trade, for a profit of 0. Checking every buy/sell pair is O(n²). The one-pass insight: if you sell on day i, the best buy day is simply the cheapest day before it, so track the minimum price so far and the best profit so far.

Example: [7, 1, 5, 3, 6, 4] → 5 (buy at 1, sell at 6).

Function signature

int maxProfit(const vector<int>& prices);  // one transaction; 0 if no profit is possible

Test cases

Input prices	Output	Explanation
[7, 1, 5, 3, 6, 4]	5	Buy at 1 (day 1), sell at 6 (day 4)
[7, 6, 4, 3, 1]	0	Prices only fall: don't trade
[2, 4, 1]	2	The later minimum (1) comes too late to help
[1]	0	Can't buy and sell on the same day
[3, 3, 3]	0
[2, 1, 2, 1, 0, 1, 2]	2	Buy at 0, sell at 2

(Confirm: exactly one buy and one later sell, or no trade at all.)

How interviewers phrase it

• "Best time to buy and sell a stock, one transaction" (LeetCode 121).
• Follow-ups: unlimited transactions (LeetCode 122), at most two or k transactions (123, 188), with a cooldown (309) or a fee (714). Those use DP.

Clarifying questions to ask

1. Only one buy and one sell?
2. Must you buy before you sell? (Yes, no short-selling.)
3. What if no profit is possible: return 0?

Follow-ups to expect

1. "Why is tracking the minimum enough?"
2. "What if you can make unlimited transactions?"
3. "How does this relate to Kadane's algorithm?"
4. "What if the array is huge and streamed?"
5. "Complexity?"

Related questions

• Assign Cookies Easy
• Lemonade Change Easy
• Jump Game - I Easy
• Kadane's Algorithm Medium
• Capacity to Ship Packages Within D Days Medium
• Jump Game II Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in