Shelf Slot for a New Book
EasyBinary SearchFree
Problem
A librarian keeps book IDs on a shelf in non-decreasing order, given as the array shelf. A new book with ID target arrives and must go in the leftmost position that keeps the shelf sorted.
Return that position: the smallest index i such that shelf[i] ≥ target, or shelf.length if every ID is smaller than target.
Example 1
- Input:
- shelf = [1, 4, 6, 9], target = 5
- Output:
- 2
5 goes between 4 and 6, so it takes index 2 and pushes 6 and 9 right.
Example 2
- Input:
- shelf = [1, 4, 6, 9], target = 6
- Output:
- 2
An equal ID is already at index 2; the new book goes in front of it.
Example 3
- Input:
- shelf = [1, 4, 6, 9], target = 10
- Output:
- 4
Constraints
- 0 ≤ shelf.length ≤ 10^5
- -10^9 ≤ shelf[i], target ≤ 10^9
- shelf is sorted in non-decreasing order (duplicates allowed).
Hint
Show the first hint
The answer can be shelf.length, so your search range must include one position past the end.
Walkthrough
How to approach it
01Clarify before coding
- If target already exists, possibly many times, which slot? The leftmost: before every equal ID.
- Can the answer be past the end? Yes, n when everything is smaller.
- Can the shelf be empty? Yes, the answer is then 0.
02Brute force
Walk from the left and stop at the first ID that is ≥ target.
Cost: O(n) time, O(1) space. Correct, but it ignores the sorted order.
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.