Find Minimum in Rotated Sorted Array
Medium · Binary Search · Array · Binary Search
Problem
An array of n distinct integers was sorted in ascending order and then rotated between 1 and n times. Rotating once moves the last element to the front, so [0,1,2,4,5,6,7] rotated 4 times is [4,5,6,7,0,1,2], and rotated n times it is sorted again.
Given the rotated array nums, return its minimum element. Your solution must run in O(log n) time.
Examples
Input: nums = [3,4,5,1,2] Output: 1
The sorted array [1,2,3,4,5] was rotated 3 times.
Input: nums = [4,5,6,7,0,1,2] Output: 0
Input: nums = [11,13,15,17] Output: 11
Rotated 4 times, so it is back in sorted order.
Constraints
- n == len(nums)
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All values in nums are distinct
- nums is sorted and rotated between 1 and n times
Approaches
- Linear scan for the drop — time O(n), space O(1)
Follow-up
What if nums may contain duplicates (LeetCode 154)? Would that change the running time, and why?
Related problems
Start free on Cariara · Coding problems · System design studio
