Watch 10 video solutions for Find Minimum in Rotated Sorted Array II, a hard level problem involving Array, Binary Search. This walkthrough by Codebix has 20,719 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
[4,5,6,7,0,1,4] if it was rotated 4 times.[0,1,4,4,5,6,7] if it was rotated 7 times.Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [1,3,5] Output: 1
Example 2:
Input: nums = [2,2,2,0,1] Output: 0
Constraints:
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums is sorted and rotated between 1 and n times.
Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
Problem Overview: You are given a sorted array that has been rotated at an unknown pivot and may contain duplicates. Your task is to return the smallest element in the array. The challenge is handling duplicates, which can break the strict ordering normally used by binary search.
Approach 1: Using Hash Maps for Optimal Time Complexity (O(n) time, O(n) space)
This approach scans the array once while storing visited values in a hash map or set-like structure. As you iterate through the array, track the smallest value seen so far. The hash map ensures constant-time lookups if you want to avoid redundant processing when duplicates appear, though the main work is still a single pass through the array. The key idea is simplicity: since duplicates make pivot detection tricky, a linear scan guarantees the correct minimum regardless of rotation. Prefer this method when constraints are small or when clarity is more important than logarithmic performance.
Approach 2: Using Sorted Arrays and Binary Search (O(log n) average time, O(1) space)
This method exploits the partially sorted structure of the rotated array. Maintain two pointers, left and right, and compute mid each iteration. If nums[mid] < nums[right], the minimum lies in the left half including mid. If nums[mid] > nums[right], the minimum must be in the right half, so move left = mid + 1. Duplicates create ambiguity when nums[mid] == nums[right]; in that case shrink the search space by decrementing right--. This preserves correctness but can degrade to O(n) in worst cases where many duplicates exist. Despite that edge case, the approach typically runs in logarithmic time and uses constant memory.
Recommended for interviews: The binary search solution is what most interviewers expect. It demonstrates understanding of rotated arrays and how duplicates affect search invariants in binary search. A linear scan or hash-based approach proves you can solve the problem correctly, but the optimized pointer-based search shows stronger algorithmic reasoning and space efficiency.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map / Linear Scan | O(n) | O(n) | Simple implementation when constraints are small or duplicates make binary search logic unnecessary |
| Binary Search on Rotated Array | O(log n) average, O(n) worst | O(1) | Preferred interview solution for rotated sorted arrays with duplicates |