162.find-peak-element.md

162. Find Peak Element

Clarification Questions

• Are there multiple peaks? And which one should we return?
• What is the value of nums[-1] and nums[n]? (n is the size of nums)

Test Cases

Normal Cases

Input: nums = [1,2,3,1]
Output: 2

Edge / Corner Cases

• Size is 1.

Input: [1]
Output: 0

• Peak is at the beginning or the end.

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

• Multiple peaks.

Input: [1,2,1,3,1]
Output: 1 or 3

Binary Search

Idea!! We always walk toward the higher position, then we will arrive at the peak eventually. (人往高處爬，水往低處流) We can apply this idea with binary search. There are several cases when choosing the middle:

1. The middle is the peak: We just return the current index.

   M 
 /   \
/     \

2. The peak is at the left part: Then we go to the left part.

 Peak 
 /   \
/     \
       M 
        \ 

3. The peak is at the right part: Then we go to the right part.

    Peak
   /   \
  /     \
 M
/

4. The middle is the lowest point: Then it's fine to go either left or right, because we will eventually arrive at the peak.

\    /
 \  /
   M   

fun findPeakElement(nums: IntArray): Int {
    // Edge case: size == 1, then it's the peak
    if (nums.size <= 1) return 0
    
    val n = nums.size

    // Two corner cases: the first and the last element is the peek
    if (nums[0] > nums[1]) return 0
    if (nums[n - 2] < nums[n - 1]) return n - 1

    // Then we search the rest range of array
    var left = 1
    var right = n - 2
    while (left <= right) {
        val middle = left + (right - left) / 2
        // Case 1. Peak is at middle
        if (nums[middle - 1] < nums[middle] && nums[middle] > nums[middle + 1]) return middle
        // Case 2. Peak is at right part
        else if (nums[middle] < nums[middle + 1]) left = middle + 1
        // Case 3. Peak is at left part
        else if (nums[middle - 1] > nums[middle]) right = middle - 1
    }
    // Dummy return
    return -1
}