Comic Book Flip
A collector's shop puts a new price on a rare comic every morning. You wrote the prices down over the past few weeks. Looking back, you wonder: if you had bought one copy on some day and sold it to another collector for that day's shop price on a later day, what is the most you could have made?
You must buy before you sell, and you can only do it once. If every possible deal loses money, you would simply not have bought.
Your task
Write bestFlip(prices). prices[i] is the price on day i. Return the largest value of prices[sell] - prices[buy] over all pairs of days with buy < sell.
If no pair makes a profit, or there are fewer than two days, return 0.
bestFlip(prices: int[]) → int
Examples
prices = [30, 22, 41, 18, 35, 27]
19
Buy on day 1 at 22 and sell on day 2 at 41 for a profit of 19. Buying at the lowest price, 18 on day 3, only gets you 35 - 18 = 17. The cheapest day is not always the best day to buy.
prices = [50, 44, 39, 31]
0
The price only falls. Every deal would lose money, so you do not trade and the answer is 0.
prices = [12, 40, 5, 9]
28
The highest price is 40 and the lowest is 5, but 5 comes after 40, so you cannot buy at 5 and sell at 40. The best real deal is 40 - 12 = 28.
Constraints
- 0 ≤ prices.length ≤ 100,000
- 0 ≤ prices[i] ≤ 100,000
Start with brute force
Try every buying day with every later selling day and keep the largest difference.
That is about n²/2 pairs. With 100,000 days it is roughly 5 billion pairs. Each selling day rescans all the earlier days to find the cheapest one, even though that answer only changes by one day at a time.
Hints
0 of 4 shown- Hint 1
Pretend you sell on day 4 in the first example, at 35. Which earlier day would you have wanted to buy on, and why?
- Hint 2
For any selling day, the best buying day is simply the cheapest day before it. So the only thing you need from the past is one number.
- Hint 3
Walk the days in order and keep the lowest price seen so far. What is the best profit if you sell today?
- Hint 4
Keep
cheapest(lowest price so far) andbest(best profit so far, starting at 0). For each price, first updatebestwithprice - cheapest, then updatecheapestwithprice.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Flip the question around. Instead of "which pair of days?", ask for each day: "if I sell today, what is my best profit?" The answer is today's price minus the cheapest price before today. Keep that cheapest price as you go, and each day costs one step.
Trace [30, 22, 41, 18, 35, 27]:
- Day 0, 30: nothing to buy from yet. cheapest = 30, best = 0.
- Day 1, 22: selling gives -8, keep best = 0. cheapest = 22.
- Day 2, 41: selling gives 41 - 22 = 19. best = 19.
- Day 3, 18: selling gives -4. cheapest = 18.
- Day 4, 35: selling gives 35 - 18 = 17, less than 19.
- Day 5, 27: selling gives 9. Final answer: 19.
Update best before cheapest. The other way round lets you buy and sell on the same day, which is harmless here (profit 0) but is a bug in problems where it is not.
function bestFlip(prices) {
let cheapest = Infinity; // lowest price on any earlier day
let best = 0; // not trading is always allowed
for (const price of prices) {
best = Math.max(best, price - cheapest); // sell today
cheapest = Math.min(cheapest, price); // or remember today as a buy
}
return best;
}def best_flip(prices):
cheapest = float("inf") # lowest price on any earlier day
best = 0 # not trading is always allowed
for price in prices:
best = max(best, price - cheapest) # sell today
cheapest = min(cheapest, price) # or remember today as a buy
return bestRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.