algoadvance

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 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.

Clarifying Questions

1. Can the array contain duplicate elements?
   • No, the elements are unique as per the problem statement.
2. Is the array always rotated?
   • The rotation can be between 1 and n times, meaning it can also be 0 times (the array is not rotated).
3. What should be returned if the array is not rotated?
   • The minimum element of an unrotated sorted array is the first element.

Strategy

To solve this problem efficiently in O(log n) time, we can use a modified binary search algorithm:

1. Initialization:
   • Set left to 0 and right to len(nums) - 1.
2. Binary Search:
   • While left is less than right:
     • Compute the middle index mid.
     • Use the property of the rotated sorted array to determine which half to search next:
       • If nums[mid] > nums[right], the smallest element is in the right half, so set left to mid + 1.
       • Otherwise, the smallest element is in the left half, so set right to mid.
3. Conclusion:
   • After the loop ends, left will point to the smallest element. Return nums[left].

Code

def findMin(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    
    return nums[left]

Time Complexity

• Time Complexity: The algorithm runs in O(log n) time because we are using a binary search approach, which halves the search space in each step.
• Space Complexity: The space complexity is O(1) because we are using only a constant amount of additional space.

This approach efficiently finds the minimum element in a rotated sorted array using properties of the rotation and binary search technique.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?