Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the Find Minimum in Rotated Sorted Array problem.

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

Given the sorted rotated array nums, return the minimum element of this array.

That's it! Now, let's dive into the solution.

Solution

We can use a binary search approach to solve this problem. Since the array is sorted in ascending order, we can compare the middle element of the array with the first and last elements to determine which half of the array to focus on. If the middle element is greater than the first element, then the minimum element must be in the second half of the array. Otherwise, the minimum element must be in the first half of the array.

We repeat this process on the chosen half of the array until we find the minimum element.

Here's the Python code for our solution:

def findMin(nums: List[int]) -> int:
    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]

Let's go through this code step-by-step.

We initialize two pointers left and right to the beginning and end of the array, respectively.

left, right = 0, len(nums) - 1

We use a while loop to repeatedly divide the array in half and narrow down the search space.

while left < right:

We calculate the middle index of the current search space.

mid = (left + right) // 2

We compare the middle element of the array with the last element of the array to determine which half of the array to focus on.

if nums[mid] > nums[right]:
    left = mid + 1
else:
    right = mid

If nums[mid] > nums[right], then we know that the minimum element must be in the second half of the array, so we set left = mid + 1. Otherwise, we know that the minimum element must be in the first half of the array, so we set right = mid.

We return the element at the left index, which should be the minimum element.

return nums[left]

Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

Time Complexity

Our solution uses binary search to find the minimum element of the rotated sorted array. Since we're dividing the search space in half at each step, the time complexity of our solution is O(log n), where n is the length of the input array.

Space Complexity

Our solution uses a constant amount of extra space to keep track of the pointers left, right, and mid. Therefore, the space complexity of our solution is O(1).

Conclusion

And there you have it! We've successfully tackled the Find Minimum in Rotated Sorted Array problem. I hope you found this blog post helpful and informative. Happy Coding! 😎

Eyuel's Blog⭐⭐⭐