šŸ”— LeetCodešŸ”— Neetcode

Find Minimum in Rotated Sorted Array

Mediumbinary searchAmazonMicrosoftMeta

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].


Given the sorted rotated array nums of unique elements, return the minimum element of this array.


You must write an algorithm that runs in **O(log n)** time.

Examples

Input:nums = [3,4,5,1,2]
Output:1
Explanation:The original array was [1,2,3,4,5] rotated 3 times.
Input:nums = [4,5,6,7,0,1,2]
Output:0
Input:nums = [11,13,15,17]
Output:11
Explanation:The original array was not rotated.

Constraints

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All integers are unique

šŸ’” Hints

Hint 1

The minimum is at the rotation point.

Hint 2

If nums[mid] > nums[right], the min is in the right half.

Hint 3

Otherwise, the min is in the left half (including mid).

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Logarithmic
Algorithmic Approach

Binary search for the inflection point. If nums[mid] > nums[right], the minimum is in the right half. Otherwise, it's in the left half (including mid).

Time ComplexityO(log n)
Why:

Binary search eliminates half of the search interval at each step by comparing nums[mid] with nums[right].

Space ComplexityO(1)
Why:

Only requires constant auxiliary index variables (left, right, mid).

Big-O Growth CurveExcellent (O(log N))
Execution time grows slowly by repeatedly halving the search space.

šŸŒ Real-World Use Cases

DatabasesLog rotation detection

Detecting the oldest entry in a circular log buffer ā€” finding the rotation point to identify the earliest timestamp.

šŸ” Dry Run

Solutionā± O(log n) | šŸ’¾ O(1)
Line2
left=0number
right=4number

Find minimum in [3,4,5,1,2]. Initialize left=0, right=4.