Find Minimum in Rotated Sorted Array II - Solution & Explanation
Problem Statement
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 rotated4times.[0,1,4,4,5,6,7]if it was rotated7times.
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] <= 5000numsis sorted and rotated between1andntimes.
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?
Approach Overview
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 1: Approach 1: Using Hash Maps for Optimal Time Complexity
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.
Complexity
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.
Approach 2: Approach 2: Using Sorted Arrays and Binary Search
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.
Complexity
Time Complexity: O(n log n) for insertion (due to sorting), O(log n) for search (binary search).
Space Complexity: O(n).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Find Minimum in Rotated Sorted Array II & l | Leetcode 154 & 153 | Hindi • Codebix • 21,204 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Minimum in Rotated Sorted Array II easy or hard?
Find Minimum in Rotated Sorted Array II Python/Java solution
How to solve Find Minimum in Rotated Sorted Array II in O(n)?
What is the best approach for Find Minimum in Rotated Sorted Array II?
Is Find Minimum in Rotated Sorted Array II asked at Google/Amazon/Meta?
What data structure is used in Find Minimum in Rotated Sorted Array II?
What is the time complexity of Find Minimum in Rotated Sorted Array II?
Ready to solve this problem?
Practice Find Minimum in Rotated Sorted Array II with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor