#154

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Minimum in Rotated Sorted Array II

Find the minimum in a rotated sorted array with possible duplicates using binary search.

Problem Statement

You are given a sorted array that has been rotated at some unknown pivot. The array may contain duplicates, making it challenging to apply standard binary search. Your task is to find the minimum element in this rotated sorted array.

For example, the array nums = [2,2,2,0,1] has been rotated, and the minimum value is 0. The array is guaranteed to contain at least one element, and the length will be between 1 and 5000.

Examples

Example 1

Input: nums = [1,3,5]

Output: 1

Example details omitted.

Example 2

Input: nums = [2,2,2,0,1]

Output: 0

Example details omitted.

Constraints

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

Solution Approach

Binary Search Approach

Use a modified binary search to divide the array into two halves. Compare the middle element with the left and right elements to decide which half to search. This ensures the algorithm works even with duplicates, where you may need to reduce the search space by skipping over duplicate values.

Handling Duplicates

When duplicates are encountered, it can be difficult to distinguish which half of the array contains the minimum. In such cases, rather than eliminating half of the array, shrink the search space by incrementing or decrementing the search boundaries until you find a unique candidate for the minimum.

Time Complexity Considerations

The solution operates in O(n) time in the worst case due to the handling of duplicates. In the average case, the time complexity can be O(log n), depending on how effectively the search space is reduced in each iteration.

Complexity Analysis

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

The worst-case time complexity is O(n) due to the need to handle duplicates, where every element might be checked. In the best case, the complexity can be reduced to O(log n) by effectively splitting the array using binary search. The space complexity is O(1) as no extra space is required beyond the input array.

What Interviewers Usually Probe

Tests how the candidate handles the trade-off between efficiency and correctness when dealing with duplicates in binary search.
Assesses the ability to modify standard algorithms (binary search) to handle edge cases, such as duplicate values and rotations.
Evaluates the candidate's ability to reason about the problem and identify when and why to adjust search boundaries in a rotated array.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the handling of duplicates, leading to inefficient solutions that don't maintain the correct time complexity.
Failing to recognize when the search space should be reduced due to duplicate values, causing the algorithm to behave like a linear search in the worst case.
Not properly handling edge cases where the array is very small or where the array contains multiple equal elements near the pivot point.

Follow-up variants

Rotate the array more times (larger rotations), requiring better insight into how the array structure behaves after multiple rotations.
Use this pattern to find the maximum value instead of the minimum by reversing the logic of the binary search.
Implement an iterative approach rather than a recursive binary search, which might better handle larger inputs with fewer function calls.

FAQ

How do I handle duplicates in this problem?

To handle duplicates, you may need to adjust the boundaries of your binary search, reducing the search space incrementally when duplicates are encountered. If duplicates are on both sides of the middle element, shift your search boundaries inward to avoid redundant checks.

Can the time complexity ever reach O(n)?

Yes, in the worst case, when the array is filled with many duplicates, the time complexity can degrade to O(n) as you may need to check every element.

What is the optimal solution for this problem?

The optimal solution uses binary search with careful handling of duplicates. This allows the time complexity to be reduced to O(log n) in many cases, but may still require O(n) in the worst case due to duplicates.

How do I know when to reduce the search space in binary search?

You should reduce the search space when the middle element is greater than the rightmost element. However, when duplicates are present, you may need to carefully compare left, middle, and right elements to ensure you're correctly narrowing down the minimum element.

Is this problem solvable without binary search?

While it's possible to solve this problem without binary search by using linear scans, binary search is preferred due to its efficiency. A linear scan would result in O(n) time complexity, which is suboptimal compared to the potential O(log n) with 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:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

Continue Practicing

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