Find Minimum in Rotated Sorted Array II
Hard · Binary Search · Array · Binary Search
Problem
An array sorted in non-decreasing order was rotated between 1 and n times: one rotation moves the last element to the front. So [0,1,4,4,5,6,7] might become [4,5,6,7,0,1,4], and n rotations give the original array back.
Unlike the distinct-values version, nums may contain duplicates. Return the minimum element, using as few steps as you can, and think about how duplicates change the worst case.
Examples
Input: nums = [2,2,2,0,1] Output: 0
The values drop from 2 to 0 at index 3, and 0 is the minimum.
Input: nums = [3,3,1,3] Output: 1
The first and last values are both 3, so they cannot tell where the drop is. The minimum is the 1.
Input: nums = [4,4,4] Output: 4
Every element is the minimum.
Constraints
- n == len(nums)
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- nums is a non-decreasing array rotated between 1 and n times
Approaches
- Scan for the drop — time O(n), space O(1)
Follow-up
Can any algorithm beat O(n) here? No: in an array of all 1s with a single 0 somewhere, every position you do not read could be the 0, so the worst case must read nearly all of them. Duplicates are what turn the logarithmic search into a linear one.
Related problems
Start free on Cariara · Coding problems · System design studio
