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.
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.
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.
Time Complexity: O(n log n) for insertion (due to sorting), O(log n) for search (binary search).
Space Complexity: O(n).
Python
Java
C++
Go
TypeScript
JavaScript
| 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). |
| Default Approach | — |
| 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 |
Find Minimum in Rotated Sorted Array II & l | Leetcode 154 & 153 | Hindi • Codebix • 20,719 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 FleetCode