Smallest Reading After Rotation
MediumBinary Search
Problem
A circular buffer of distinct temperature readings was written in increasing order, but the dump starts at an arbitrary slot, so the array temps is a sorted array rotated by an unknown amount.
Return the smallest reading in O(log n) time.
Example 1
- Input:
- temps = [5, 7, 9, 1, 2]
- Output:
- 1
The original order was [1, 2, 5, 7, 9], rotated so that it starts at 5.
Example 2
- Input:
- temps = [10, 20, 30]
- Output:
- 10
No rotation: the first element is the minimum.
Constraints
- 1 ≤ temps.length ≤ 10^5
- -10^9 ≤ temps[i] ≤ 10^9
- All values are distinct.
Hint
Show the first hint
Compare an element with the last element of the array. What does it tell you about which side of the drop it is on?
Walkthrough
How to approach it
01Clarify before coding
- Are readings distinct? Yes.
- Can the rotation be zero? Yes: then the first element is the minimum.
- Return the value or the index? The value.
02Brute force
Take the minimum of the whole array, or scan for the single place where temps[i] > temps[i + 1].
Cost: O(n) time, O(1) space.
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.