543. Find minimum in rotated sorted array - II
0
Hard
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** , Print the minimum element of this array.
***Note : You must decrease the overall operation steps as much as possible.***
Input Format
First line contains an integer n.
Second line contains an integer array nums.
Second line contains an integer array nums.
Output Format
Print the minimum element of the array.
Example
Input
5
3 3 3 1 2
Output
1
Constraints
* 1 <= n <= 105
* -104 <= nums[i] <= 104
* nums is sorted and rotated between 1 and n times.
* -104 <= nums[i] <= 104
* nums is sorted and rotated between 1 and n times.
Loading...
View Submissions
Console