Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Find Min/Max in Rotated Sorted Array subpattern.
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,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,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 of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Constraints:
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique.
- nums is sorted and rotated between 1 and n times.
Topics and companies
Topics: Array, Binary Search.
Reported in interviews at Facebook, Amazon, Bloomberg, Goldman Sachs, Microsoft, Oracle.
How to practise Find Minimum in Rotated Sorted Array on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.
Open Find Minimum in Rotated Sorted Array in the code editor, or read the Find Minimum in Rotated Sorted Array editorial for a worked solution with its approach and complexity analysis.
Where Find Minimum in Rotated Sorted Array sits in the DSA pattern sheet
- Binary Search Patterns pattern guide
- Find Min/Max in Rotated Sorted Array subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Find Minimum in Rotated Sorted Array
Other problems that use the same Find Min/Max in Rotated Sorted Array and Binary Search Patterns techniques:
- Find in Mountain Array — Hard, same subpattern
- Find Peak Element — Medium, same subpattern
- Peak Index in a Mountain Array — Medium, same subpattern
- Search in Rotated Sorted Array — Medium, same subpattern
- Search in Rotated Sorted Array II — Medium, same subpattern
- Binary Search — Easy, same pattern