153. Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
---
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
Intuition
Sorted Array => Binary search with unknown target
Target is pivot .. or min element
Need to identify appropriate half to search
Make use of pivot relative to mid
while (lo <= hi)
if (lo == hi)
=> base case
=> terminate
=> return arr[lo]
if (arr[mid] < arr[hi])
=> strictly increasing upper half
=> discard upper half
=> mid is potential answer since its smaller
=> hi = mid
else
=> given no duplicates => arr[mid] > arr[hi]
=> pivot is somewhere between mid and hi
=> discard mid since it is higher .. cannot be ans
=> lo = mid + 1
---
Time - O(log N)
Space - O(1)
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int findMin(int[] nums) { | |
| // Optimization - skip the binary search | |
| if (nums[0] < nums[nums.length - 1]) { | |
| return nums[0]; | |
| } | |
| int lo = 0, hi = nums.length - 1; | |
| int ans = nums[lo]; | |
| while (lo <= hi) { | |
| int mid = lo + (hi - lo)/2; | |
| if (lo == hi) { | |
| return nums[lo]; | |
| } | |
| // If mid < hi .. mid is still a candidate for min, dont discard it | |
| if (nums[mid] < nums[hi]) { | |
| hi = mid; | |
| } else { | |
| // mid > hi => discard mid .. mid cannot be lowest element | |
| lo = mid + 1; | |
| } | |
| } | |
| return -1; | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def findMin(self, nums: List[int]) -> int: | |
| lo = 0 | |
| hi = len(nums) - 1 | |
| if lo == hi or nums[lo] < nums[hi]: | |
| return nums[lo] | |
| while lo <= hi: | |
| mid = lo + (hi - lo) // 2 | |
| if nums[mid + 1] < nums[mid]: | |
| return nums[mid + 1] | |
| if nums[mid] < nums[mid - 1]: | |
| return nums[mid] | |
| if nums[lo] < nums[mid]: | |
| lo = mid + 1 | |
| else: | |
| hi = mid - 1 | |
| return nums[hi] |
Related problems
---
