New Dish on the Menu
A small café prints its menu with dishes listed from cheapest to most expensive. Prices are stored in cents, so 420 means 4.20. Two dishes can cost the same.
The cook has a new dish and a price for it. The printer needs to know which line the new dish goes on so the menu stays sorted. If other dishes already have that exact price, the new one is listed before them, so the newest dish gets seen first.
Your task
Write insertPosition(prices, price). prices is sorted from smallest to largest and may contain repeats. Return the index where price should be inserted: the first index whose price is greater than or equal to price. If every price is smaller, return prices.length.
Do not change the list. An empty menu returns 0. Aim for O(log n).
insertPosition(prices: int[], price: int) → int
Examples
prices = [350, 420, 420, 575, 890] price = 500
3
350, 420 and 420 are all cheaper than 500. The first price that is 500 or more is 575, at index 3, so the new dish goes there and pushes 575 down a line.
prices = [350, 420, 420, 575, 890] price = 420
1
Two dishes already cost 420. The new one goes before both of them, at index 1. Index 3 (after them) would be a valid sorted spot too, but the café's rule says before.
Constraints
- 0 ≤ prices.length ≤ 100,000
- 1 ≤ prices[i], price ≤ 100,000
- prices is sorted in non-decreasing order.
Start with brute force
Walk from the start and return the first index whose price is at least price, or n if you reach the end.
That is O(n): up to 100,000 checks for one dish. A plain binary search that stops as soon as it finds an equal price is faster but wrong here: in the second example its first look lands on index 2, one of the two 420s, and it returns 2 instead of 1.
Hints
0 of 4 shown- Hint 1
In
[350, 420, 420, 575, 890], mark each price as "smaller than 500" or "not". What shape does that row of marks have? - Hint 2
It is always a block of "smaller" followed by a block of "not smaller", because the list is sorted. You want the first position of the second block.
- Hint 3
Binary search for that boundary instead of for a value. If the middle price is smaller than
price, the boundary is to its right. Otherwise the middle itself might be the boundary, so you cannot throw it away. - Hint 4
Start with
lo = 0andhi = n(one past the end, because the answer can ben). Whilelo < hi: ifprices[mid] < pricesetlo = mid + 1, elsehi = mid. When they meet, that is the answer.
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
Instead of searching for a value, search for a boundary: the first price that is not smaller than the new one. Everything left of it is smaller, everything from it on is not.
Trace [350, 420, 420, 575, 890] with price 420:
lo = 0,hi = 5,mid = 2. 420 is not smaller than 420, so index 2 might be the boundary.hi = 2.lo = 0,hi = 2,mid = 1. 420 again.hi = 1.lo = 0,hi = 1,mid = 0. 350 < 420, so the boundary is to the right.lo = 1.lo = hi = 1. Return 1.
Two details make this work. First, hi starts at n, not n - 1, because "after everything" is a valid answer. Second, when the middle is big enough you set hi = mid, not mid - 1: the middle might be the answer itself. The loop still ends, because mid is always strictly less than hi.
function insertPosition(prices, price) {
let lo = 0, hi = prices.length; // the answer is somewhere in [lo, hi]
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (prices[mid] < price) lo = mid + 1; // mid is too cheap: boundary is right of it
else hi = mid; // mid could be the boundary: keep it
}
return lo;
}def insert_position(prices, price):
lo, hi = 0, len(prices) # the answer is somewhere in [lo, hi]
while lo < hi:
mid = (lo + hi) // 2
if prices[mid] < price:
lo = mid + 1 # mid is too cheap: boundary is right of it
else:
hi = mid # mid could be the boundary: keep it
return loRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.