Find Minimum in Rotated Sorted Array - LeetCode Problem

Search for a command to run...

No comments yet. Be the first to comment.
Problem Description Welcome back! Today, we'll be solving the Reverse Linked List problem on LeetCode. Given the head of a singly linked list, reverse the list, and return the reversed list's head. For example, if the input linked list is 1 -> 2 -> 3...

Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Guess Number Higher or Lower problem. You are playing the Guess Game with your friend. In this game, your friend thinks of a number between 1 and n, and you hav...

Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Search 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 = [...

Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Min Stack problem. Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop...

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.
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.
left and right to the beginning and end of the array, respectively.left, right = 0, len(nums) - 1
while loop to repeatedly divide the array in half and narrow down the search space.while left < right:
mid = (left + right) // 2
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.
left index, which should be the minimum element.return nums[left]
Now that we have our solution, let's analyze its time and space 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.
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).
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! 😎