An array of distinct integers was sorted in ascending order and then rotated some number of times (possibly zero), for example [0,1,2,4,5,6,7] could become [4,5,6,7,0,1,2]. Return the smallest element. Your solution must be O(log n).
- 1 <= nums.length <= 5000
- -5000 <= nums[i] <= 5000
- All values are distinct
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Taking the minimum with a scan is O(n). Think of the rotated array as two sorted runs, where every value in the first run is bigger than every value in the second. The minimum is the first element of the second run. Comparing nums[mid] with the last element tells us which run mid is in: if nums[mid] > nums[hi], mid is in the first run and the minimum lies to the right. Otherwise mid is in the second run, so the minimum is mid or something left of it. Shrinking until lo == hi lands on the minimum.
Algorithm
- Set
lo = 0,hi = n - 1. - While
lo < hi, computemid. - If
nums[mid] > nums[hi], setlo = mid + 1. - Otherwise set
hi = mid. - Return
nums[lo].
O(log n)Space: O(1)nums[hi], not nums[lo]. Comparing with the left end breaks on an array that was not rotated at all, like [1,2,3,4]. The follow-up with duplicates needs hi-- when nums[mid] == nums[hi], which makes the worst case O(n).class Solution: def findMin(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] > nums[hi]: lo = mid + 1 # mid is in the bigger first run else: hi = mid # minimum is mid or to its left return nums[lo]