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