DEV Community

Riyaz
Riyaz

Posted on

Find minimum in rotated sorted array in Python(code and explanation)

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.
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)