Problem
An array arr
is a mountain if the following properties hold:
arr.length >= 3
There exists somei
with0 < i < arr.length - 1
such that:arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr
, return the index i
such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
.
You must solve it in O(log(arr.length))
time complexity.
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
Constraints:
3 <= arr.length <= 105
0 <= arr[i] <= 106
arr
is guaranteed to be a mountain array.
Solution
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
var left = 0;
var right = arr.length - 1;
while (left < right) {
var mid = left + Math.floor((right - left) / 2);
if (arr[mid] > arr[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
Explain:
nope.
Complexity:
- Time complexity : O(log(n)).
- Space complexity : O(1).