Find the Minimum in a Rotated Sorted Array
Company: Point72
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find the Minimum in a Rotated Sorted Array
A strictly increasing array of distinct integers has been rotated at an unknown pivot. Return its minimum value. The array may be unrotated.
## Function Contract
Implement `find_rotated_min(nums) -> int`.
## Constraints
- 1 <= array length <= 200000.
- All elements are distinct integers between -10^9 and 10^9.
- The input is a rotation of one strictly increasing array.
- The expected time complexity is O(log n).
## Examples
```text
nums = [4, 5, 6, 7, 0, 1, 2]
output = 0
```
```text
nums = [1, 2, 3]
output = 1
```
```hint Exercise pivot boundaries
Test an unrotated array and rotations whose pivot is near either end.
```
```hint Honor the target complexity
A full scan can return the right value but does not meet the required logarithmic bound.
```
Quick Answer: A strictly increasing array of distinct integers has been rotated at an unknown pivot. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
A nonempty strictly increasing array of distinct integers has been rotated at an unknown pivot and may also be unrotated. Return its minimum value in O(log n) time.
Constraints
- 1 <= len(nums) <= 200000.
- Every value is a distinct integer from -10^9 through 10^9.
- nums is a rotation, possibly by zero positions, of one strictly increasing array; expected time is O(log n).
Examples
Input: ([5],)
Expected Output: 5
Explanation: A one-element array has that element as its minimum.
Input: ([4, 5, 6, 7, 0, 1, 2],)
Expected Output: 0
Explanation: A middle pivot places zero at the rotation boundary.
Hints
- Test a one-element array, an unrotated array, and rotations whose pivot is near either end.
- Include both negative and positive values and both allowed numeric boundaries.
- Use a large valid rotation when checking the required logarithmic time bound.