852. Peak Index in a Mountain Array #

Problem #

Let’s call an array A a mountain if the following properties hold:

A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

Summary #

We call an array A that satisfies the following properties a mountain:

A.length >= 3
There exists 0 < i < A.length - 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] Given an array that is definitely a mountain, return any value of i that satisfies A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1].

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain as defined above

Solution Ideas #

Given an array, there exists exactly one “peak” in the array (the definition of a peak is that the element at index i is greater than the elements at positions i-1 and i+1). Find this “peak” and output the index of one peak.
This problem can be solved directly with binary search. The elements in the array are basically ordered. The condition for determining whether it is a peak is to compare the two numbers on the left and right: if the current number is greater than both the left and right numbers, then the peak has been found. All other cases are on a slope. There are two ways to write this problem: the first is the standard binary search method, and the second is a variant binary search method.

Code #


package leetcode

// Solution 1: Binary search
func peakIndexInMountainArray(A []int) int {
	low, high := 0, len(A)-1
	for low <= high {
		mid := low + (high-low)>>1
		if A[mid] > A[mid+1] && A[mid] > A[mid-1] {
			return mid
		}
		if A[mid] > A[mid+1] && A[mid] < A[mid-1] {
			high = mid - 1
		}
		if A[mid] < A[mid+1] && A[mid] > A[mid-1] {
			low = mid + 1
		}
	}
	return 0
}

// Solution 2: Binary search
func peakIndexInMountainArray1(A []int) int {
	low, high := 0, len(A)-1
	for low < high {
		mid := low + (high-low)>>1
		// If mid is larger, then a peak exists on the left, high = m; if mid + 1 is larger, then a peak exists on the right, low = mid + 1
		if A[mid] > A[mid+1] {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}