One Trade Profit
Problem
prices[i] is the price of a collectible on day i. You may buy it once and sell it once, on a later day than the purchase.
Return the largest profit you can make. If no trade makes money, return 0 (you simply do not trade).
Example 1
- Input:
- prices = [7, 1, 5, 3, 6, 4]
- Output:
- 5
Buy on day 1 at 1 and sell on day 4 at 6.
Example 2
- Input:
- prices = [9, 7, 4, 1]
- Output:
- 0
Prices only fall, so you stay out.
Constraints
- 1 ≤ prices.length ≤ 10^5
- 0 ≤ prices[i] ≤ 10^4
Hint
Show the first hint
If you sell on day i, which buy day is best?
Walkthrough
How to approach it
01Clarify before coding
- Can I buy and sell on the same day? That earns 0, which is the same as not trading, so it does not matter.
- Must I trade? No; return 0 when every trade loses.
- Only one buy and one sell? Yes.
02Brute force
Try every pair buy day i < sell day j and keep the largest prices[j] - prices[i].
Cost: O(n²) time: 5·10^9 pairs for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.