Problem statement
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] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-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.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Intuition
From the question we can easily understand that it is a Binary Search question(Hints - Sorted and expectedTime Complexity-logn).
But we cannot directly apply it.
Implementation
So if the array is rotated then we can say that now the entire array is divided into two different sorted arrays.
for eg.
[6, 7, 8, 1, 4]
0 1 2 3 4
from index 0 to 2 the array is sorted and from index 3 to 3 the array is sorted.
But from index 2 to 3 the array is not sorted.
Also we can say that if any number from array is greater than its first element than it is sorted.Then we will look for our number in right part of array i.e
l = mid + 1
And if any number is less than its first element than it is not sorted from first index to mid.Then we will look for our number in left part of array i.e
h = mid - 1
Also in the array the smallest number will be the number that is smaller than both its previous and next element
Hence we will check
if nums[mid] < nums[mid-1]:
return nums[mid]
if nums[mid+1] < nums[mid]:
return nums[mid+1]
Code
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
l, h = 0, len(nums)-1
if nums[h] > nums[0]:
return nums[0]
while l <= h:
mid = (l+h)//2
if nums[mid] < nums[mid-1]:
return nums[mid]
if nums[mid+1] < nums[mid]:
return nums[mid+1]
if nums[mid] > nums[0]:
l = mid + 1
else:
h = mid - 1
Time Complexity
O(logn) as we are using binary search itself with some changes.
Space Complexity
O(1) No extra space required similar to binary search.
Top comments (0)