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 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).
This approach utilizes hash maps (dictionaries in Python) to achieve optimal time and space complexity for operations such as insertion, deletion, and lookup. By storing elements as keys in a hash map, we benefit from average-case O(1) time complexity for these operations.
In C, hash maps aren't natively supported, so we implement it using separate chaining. We map keys to a list at each index using a simple modulo-based hash function.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) on average for search, insert, and delete due to the hash map.
Space Complexity: O(n), where n is the number of elements stored.
This approach leverages sorted arrays to perform efficient binary searches. Operations are optimized for scenarios requiring sorted data, such as when frequent minimum/maximum queries are performed.
In C, we maintain sorted arrays using qsort after each insertion. Searches are performed with a custom binary search function for efficiency.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) for insertion (due to sorting), O(log n) for search (binary search).
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Approach 1: Using Hash Maps for Optimal Time Complexity | Time Complexity: O(1) on average for search, insert, and delete due to the hash map. |
| Approach 2: Using Sorted Arrays and Binary Search | Time Complexity: O(n log n) for insertion (due to sorting), O(log n) for search (binary search). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Linear Scan | O(n) | O(n) | Simple implementation or when rotation properties are ignored |
| Modified Binary Search | Average O(log n), Worst O(n) | O(1) | Interview-preferred solution for rotated sorted arrays with duplicates |
Find Minimum in Rotated Sorted Array - Binary Search - Leetcode 153 - Python • NeetCode • 356,602 views views
Watch 9 more video solutions →Practice Find Minimum in Rotated Sorted Array II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor