Reference: LeetCode
Difficulty: Medium

Problem

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example: 

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
1
2
3
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Follow up: Your solution should be in logarithmic time complexity.

Analysis

Brute-Force

Note: Use long type.

1
2
3
4
5
6
7
8
9
10
11
public int findPeakElement(int[] nums) {
  int n = nums.length;
  for (int i = 0; i < n; ++i) {
    long left = (i - 1 < 0) ? Long.MIN_VALUE : nums[i - 1];
    long right = (i + 1 > n - 1) ? Long.MIN_VALUE : nums[i + 1];
    if (nums[i] > left && nums[i] > right) {
      return i;
    }
  }
  return -1;
}

Another version in one if:

1
2
3
4
5
6
7
8
9
public int findPeakElement(int[] nums) {
  int n = nums.length;
  for (int i = 0; i < n; ++i) {
    if ((i <= 0 || nums[i] > nums[i - 1]) && (i >= n - 1 || nums[i] > nums[i + 1])) {
      return i;
    }
  }
  return -1;
}

If we exploit all test cases, we know that the peak must occur in all cases. In other words, the peak is guaranteed.

Illustration

1
2
3
4
[1]        // only one element
[1  2  3]  // in ascending order - last element
[3  2  1]  // in descending order - first element
[1  2  3  1] // in the middle

So we just need to check whether there is nums[i] > nums[i + 1] in the array. If not, return the last index as the answer.

The solution version:

1
2
3
4
5
6
7
8
public int findPeakElement(int[] nums) {
  int n = nums.length;
  for (int i = 0; i < n - 1; ++i) {
    if (nums[i] > nums[i + 1])
      return i;
  }
  return n - 1; // last index
}

Time: $O(N)$
Space: $O(1)$

The reason why we can use binary search for this problem is that when the current trend is ascending or descending we can determine which side to go.

  • \ or nums[mid] > nums[mid + 1] or descending: At least one peak lies on the left side, although there is possibly another one on the right side.
  • / or nums[mid] < nums[mid + 1] or ascending: At least one peak lies on the right side, although there is possibly another one on the left side.
  • Equal case is not possible.

Why do we use lo < hi and hi = mid?

a. lo < hi:

  • lo and hi will point to the same element at last.
  • If it is lo <= hi, lo will be eventually larger than hi and lo may be out of bound, which is not allowed in this problem.
  • Consider the case [1]. If lo <= hi is applied, the code inside the loop will be executed and nums[mid + 1] will be out of bound! So lo < hi makes sure that this won’t happen.

b. hi = mid:

  • If / or nums[mid] < nums[mid + 1], we update lo by mid + 1 since the element at mid cannot be the peak.
  • If \ or nums[mid] > nums[mid + 1], we update hi by mid instead of mid - 1 since the element at mid could be the peak.
1
2
3
4
5
6
7
8
9
10
11
12
13
public int findPeakElement(int[] nums) {
  int n = nums.length;
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] > nums[mid + 1]) { // descending
      hi = mid;
    } else { // ascending
      lo = mid + 1;
    }
  }
  return lo;
}

Time: $O(\log{N})$
Space: $O(1)$