Rotated Shelf With Repeats
MediumBinary Search
Problem
Stock counts on a shelf were recorded in non-decreasing order and then rotated at an unknown pivot. Unlike a clean roster, values may repeat.
Given the rotated array stock and a value target, return true if target appears in it and false otherwise. Keep the average case logarithmic.
Example 1
- Input:
- stock = [4, 5, 5, 6, 1, 2, 4], target = 1
- Output:
- true
Example 2
- Input:
- stock = [4, 5, 5, 6, 1, 2, 4], target = 3
- Output:
- false
Example 3
- Input:
- stock = [1, 0, 1, 1, 1], target = 0
- Output:
- true
Here stock[lo], stock[mid] and stock[hi] are all 1, so they say nothing about which half is sorted.
Constraints
- 1 ≤ stock.length ≤ 5000
- -10^4 ≤ stock[i], target ≤ 10^4
- stock is a non-decreasing array rotated at some pivot.
Hint
Show the first hint
Start from the distinct-values version: decide which half is sorted by comparing stock[lo] and stock[mid].
Walkthrough
How to approach it
01Clarify before coding
- Is a boolean enough, or do you need the index? A boolean.
- How bad can duplicates get? Arbitrarily: the array could be all one value with a single different element.
- Is O(log n) worst case required? It is impossible here; logarithmic on average, O(n) worst case is the expected answer.
02Brute force
Scan the array for target.
Cost: O(n) time. It is also the worst case of the optimal method, but the optimal one is O(log n) whenever duplicates do not hide the pivot.
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.