557. Minimum Element in a Rotated Sorted Array
0
Medium
Given an array of length n that is sorted in ascending order and has been rotated between 1 and n times, find the minimum element in the array. For example, if the original array nums = [0,1,2,4,5,6,7], it might become:
[4,5,6,7,0,1,2] after being rotated 4 times.
[0,1,2,4,5,6,7] after being rotated 7 times.
Note that rotating an array [a[0], a[1], a[2], ..., a[n-1]] once results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. You need to write an algorithm that has a time complexity of O(log n).
[0,1,2,4,5,6,7] after being rotated 7 times.
Note that rotating an array [a[0], a[1], a[2], ..., a[n-1]] once results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. You need to write an algorithm that has a time complexity of O(log n).
Input Format
The first line contains the size of the array
The second line contains the elements of the array
The second line contains the elements of the array
Output Format
Print the minimum element as an integer
Example
Input
5
3 4 5 1 2
Output
1
Constraints
n is equal to the length of the array
1 is less than or equal to n and n is less than or equal to 5000
Each element in the array is an integer between -5000 and 5000
All integers in the array are unique
The array is sorted and has been rotated between 1 and n times
1 is less than or equal to n and n is less than or equal to 5000
Each element in the array is an integer between -5000 and 5000
All integers in the array are unique
The array is sorted and has been rotated between 1 and n times
Loading...
View Submissions
Console