Katkat
Back

Find the Minimum in a Rotated Sorted Array

Point72Quantitative Researcher · Technical Screen
MediumQuantitative ResearcherTechnical ScreenCoding & Algorithms

Last updated

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.

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

nums = [4, 5, 6, 7, 0, 1, 2]
output = 0

nums = [1, 2, 3]
output = 1

Hints

Hint 1

Exercise pivot boundaries: Test an unrotated array and rotations whose pivot is near either end.

Hint 2

Honor the target complexity: A full scan can return the right value but does not meet the required logarithmic bound.