#153

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Minimum in Rotated Sorted Array

Find the minimum element in a rotated sorted array using binary search to efficiently identify the point of rotation.

Problem Statement

Given a sorted array that has been rotated between 1 and n times, the task is to find the minimum element in this rotated array. The array contains unique integers and can be as large as 5000 elements. The array was originally sorted in ascending order, and now it's been rotated.

For example, the array nums = [3, 4, 5, 1, 2] was originally [1, 2, 3, 4, 5] but was rotated 3 times. The goal is to return the minimum element in the array, which in this case would be 1. You need to implement an efficient algorithm to solve this problem.

Examples

Example 1

Input: nums = [3,4,5,1,2]

Output: 1

The original array was [1,2,3,4,5] rotated 3 times.

Example 2

Input: nums = [4,5,6,7,0,1,2]

Output: 0

The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3

Input: nums = [11,13,15,17]

Output: 11

The original array was [11,13,15,17] and it was rotated 4 times.

Constraints

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

Solution Approach

Binary Search Approach

The optimal solution to this problem leverages binary search. Since the array is rotated, there is a pivot point where the order of elements changes. By comparing the middle element with the rightmost element, we can determine which half of the array contains the minimum. This approach has a time complexity of O(log n).

Identifying the Pivot

The core idea behind binary search for this problem is to identify the pivot where the array rotation occurred. The left side of the pivot will always contain larger elements, while the right side will contain the smaller elements. By adjusting the search boundaries based on the pivot comparison, we can efficiently find the minimum element.

Edge Case Consideration

It's important to consider edge cases like when the array is not rotated at all (the array is already in ascending order). In such cases, the first element is the minimum, and no rotation needs to be considered. The binary search will handle this scenario without any issues.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(log n) due to the binary search method, where n is the length of the array. This is optimal for large arrays, as each iteration halves the search space. The space complexity is O(1) since the algorithm does not require extra space for data storage.

What Interviewers Usually Probe

Candidate demonstrates understanding of binary search for searching in rotated arrays.
Candidate is able to identify the pivot point and explain how binary search narrows down the minimum element.
Candidate should address edge cases and explain the solution's efficiency.

Common Pitfalls or Variants

Common pitfalls

Incorrectly identifying the pivot, leading to an inefficient or incorrect solution.
Not handling the case where the array is not rotated, resulting in unnecessary computations.
Using a brute force approach (O(n)) instead of binary search, missing the performance benefits.

Follow-up variants

Find the maximum element in a rotated sorted array.
Find the minimum element in a rotated sorted array with duplicate elements.
Find the rotation point in the array without explicitly finding the minimum element.

FAQ

What is the main algorithmic approach for solving the 'Find Minimum in Rotated Sorted Array' problem?

The main approach is binary search, which allows you to identify the pivot point in the rotated array and find the minimum element in O(log n) time.

How does binary search work in the context of finding the minimum in a rotated array?

In binary search, the array is split into two halves. By comparing the middle element with the rightmost element, we can determine which half contains the minimum, narrowing the search range until we find it.

What is the time complexity of the solution for this problem?

The time complexity is O(log n) because binary search reduces the problem size by half with each iteration, making it much more efficient than a brute-force O(n) solution.

Are there any edge cases I need to consider when solving this problem?

Yes, edge cases include when the array is not rotated at all, where the first element will be the minimum. Also, consider arrays with only one element, where the minimum is trivially the single element.

Can I solve this problem using a brute-force approach?

While a brute-force solution with O(n) time complexity will work, it is less efficient compared to the optimal O(log n) solution using binary search.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] <= nums[-1]:
            return nums[0]
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[0] <= nums[mid]:
                left = mid + 1
            else:
                right = mid
        return nums[left]

Continue Practicing

#154 find minimum in rotated sorted array ii #162 find peak element #167 two sum ii input array is sorted