Finding Minimum in Rotated Sorted Array

Finding Minimum in Rotated Sorted Array

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.

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

Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Approach 1:

The part that really threw me off was the fact that this had to be done in O(log n) time. I cannot simply iterate through the list since that will incur O(n) time. I have to do something like divide and conquer… maybe utilize binary search in some way?

I knew binary search takes O(log n) time to find the index of an element in an array, and that is the only algorithm I could come up with that can do that in that efficient time. Given that the given array is sort of sorted, I became certain that I could use logics similar to that of binary search.

But how?

Since we are not guaranteed a sorted list, we cannot just simply copy and paste binary search implementation. Here is my systematic approach:

1. Check if the len(nums) == 1 or if it is already sorted –> return nums[0] immediately
2. Initialize lo,hi,mid values to find the discontinuity in the array (‘critical point’ in which it is decrementing)
3. If nums[mid+1] > nums[mid] –> return nums[mid + 1]
4. If nums[mid-1] > nums[mid] –> return nums[mid]
5. Else, update lo = mid + 1 or high = mid

Implementation:

class Solution:


    def findMin(self, nums):
        if len(nums) == 1 or nums[-1] > nums[0]:
            return nums[0]
        lo,hi = 0, len(nums) - 1
        while hi >= lo:
            mid = lo + (hi - lo) // 2
            if nums[mid] > nums[mid + 1]:
                return nums[mid+1]
            if nums[mid - 1] > nums[mid]:
                return nums[mid]
            if nums[mid] > nums[0]:
                lo = mid + 1
            else:
                hi = mid - 1
        

Complexity Analysis:

Time Complexity:O(log n) where n is the length of the list

Space Complexity: O(1)

Reflection

Through this questions, I learned that using a binary search whenever there is a sorted list might be an idea. I feel like it is thins kind of intuition that really will prepare me for the interview questions.

Let’s not get discouraged by the fact that I was not able to solve the question within 30 minutes, but be thankful for my effort:)