Similar Problems

Similar Problems not available

Find Minimum In Rotated Sorted Array

Companies:

LeetCode:  Find Minimum In Rotated Sorted Array Leetcode Solution

Difficulty: Unknown

Topics: array binary-search  

The problem "Find Minimum in Rotated Sorted Array" on LeetCode can be solved efficiently using the Binary Search algorithm. The problem statement is as follows:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in the array.

You may assume no duplicate exists in the array.

Example 1: Input: [3,4,5,1,2] Output: 1

Example 2: Input: [4,5,6,7,0,1,2] Output: 0

To solve this problem, we can make use of Binary Search algorithm by finding the pivot element. The pivot element is the minimum element in the array and it is the element that is the result of rotation of the original sorted array.

The approach to solve this problem is as follows:

  1. Initialize left and right pointers to the start and end of the array respectively.

  2. While the left pointer is less than the right pointer, compute the mid value as (left + right) / 2.

  3. If the mid value is greater than the element at the right pointer, then shift the left pointer i.e., left = mid + 1.

  4. Otherwise, shift the right pointer i.e., right = mid.

  5. Once the while loop terminates, the minimum element will be at the left pointer.

The implemented code in Python is as follows:

class Solution: def findMin(self, 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]

Solution Implementation

1