Find Minimum in Rotated Sorted Array II - Video Solutions

Problem Overview: You are given a rotated sorted array that may contain duplicate values. The task is to return the smallest element. Rotation breaks the global ordering, but parts of the array remain sorted, which allows you to exploit binary search or perform a linear scan using auxiliary structures.

Approach 1: Using Hash Maps for Optimal Time Complexity (O(n) time, O(n) space)

This approach performs a single pass through the array while storing elements in a hash map or set-like structure. Each value is processed once and the minimum value is tracked during iteration. The hash structure prevents redundant checks if duplicates appear multiple times. Because every element is visited exactly once, the runtime is O(n) and the auxiliary memory usage is O(n). This method does not rely on the rotated sorted property, so it works even if the ordering information becomes unreliable due to heavy duplication.

From an implementation perspective, you iterate through the array, insert values into a hash map, and update a running minimum using min(currentMin, nums[i]). While straightforward, this solution ignores the structure that rotation gives you, so it is rarely the preferred interview solution.

Approach 2: Using Sorted Arrays and Binary Search (Average O(log n), Worst O(n) time, O(1) space)

The more interesting approach uses modified binary search. In a rotated sorted array, the minimum element lies at the pivot where the sorted order breaks. You maintain two pointers left and right and repeatedly check the middle index. If nums[mid] < nums[right], the minimum must be in the left half including mid. If nums[mid] > nums[right], the pivot lies in the right half, so move left = mid + 1.

Duplicates introduce ambiguity. When nums[mid] == nums[right], the algorithm cannot determine which side contains the pivot. The safe move is to shrink the search space by decrementing right--. This preserves correctness but may degrade the runtime to O(n) in the worst case (for example when most values are identical). In typical cases, the search still behaves close to O(log n) with constant space.

Recommended for interviews: The modified binary search is what interviewers expect. A linear or hash-based scan demonstrates baseline problem solving, but recognizing the rotated structure and applying binary search shows deeper algorithmic understanding. Mention the duplicate edge case explicitly and explain why the worst-case time can degrade to O(n).