Welcome to Subscribe On Youtube

852. Peak Index in a Mountain Array

Description

An array arr is a mountain if the following properties hold:

• arr.length >= 3
• There exists some i with 0 < 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.

Solutions

Binary search.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript

• class Solution { public int peakIndexInMountainArray(int[] arr) { int left = 1, right = arr.length - 2; while (left < right) { int mid = (left + right) >> 1; if (arr[mid] > arr[mid + 1]) { right = mid; } else { left = mid + 1; } } return left; } } 

• class Solution { public: int peakIndexInMountainArray(vector<int>& arr) { int left = 1, right = arr.size() - 2; while (left < right) { int mid = (left + right) >> 1; if (arr[mid] > arr[mid + 1]) right = mid; else left = mid + 1; } return left; } }; 

• class Solution: def peakIndexInMountainArray(self, arr: List[int]) -> int: left, right = 1, len(arr) - 2 while left < right: mid = (left + right) >> 1 if arr[mid] > arr[mid + 1]: right = mid else: left = mid + 1 return left 

• func peakIndexInMountainArray(arr []int) int { left, right := 1, len(arr)-2 for left < right { mid := (left + right) >> 1 if arr[mid] > arr[mid+1] { right = mid } else { left = mid + 1 } } return left } 

• function peakIndexInMountainArray(arr: number[]): number { let left = 1, right = arr.length - 2; while (left < right) { const mid = (left + right) >> 1; if (arr[mid] > arr[mid + 1]) { right = mid; } else { left = mid + 1; } } return left; } 

• /** * @param {number[]} arr * @return {number} */ var peakIndexInMountainArray = function (arr) { let left = 1; let right = arr.length - 2; while (left < right) { const mid = (left + right) >> 1; if (arr[mid] > arr[mid + 1]) { right = mid; } else { left = mid + 1; } } return left; }; 

• impl Solution { pub fn peak_index_in_mountain_array(arr: Vec<i32>) -> i32 { let mut left = 1; let mut right = arr.len() - 2; while left < right { let mid = left + (right - left) / 2; if arr[mid] > arr[mid + 1] { right = mid; } else { left = left + 1; } } left as i32 } } 

All Problems

All Solutions