162. Find Peak Element

2020, Dec 05 2 mins read

1. Description

A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.

2. Example

Example 1

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2

Input: nums = [1,2,1,3,5,6,4]
Output: 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.

3. Constraints

1 <= nums.length <= 1000
$-2^{31}$ <= nums[i] <= $2^{31}$ - 1
nums[i] != nums[i + 1] for all valid i.

4. Solutions

Binary Search

n = nums.size()
Time complexity: O(logn)
Space complexity: O(1)

class Solution {
public:
    int findPeakElement(const vector<int> &nums) {
        const int n = nums.size();
        int left = 0, right = n;
        while (left < right) {
            int middle = left + (right - left) / 2;

            if ((middle == 0 || nums[middle] > nums[middle - 1]) &&
                (middle == n - 1 || nums[middle] < nums[middle + 1])) {
                left = middle + 1;
            } else if (
                (middle == 0 || nums[middle] > nums[middle - 1]) &&
                (middle == n - 1 || nums[middle] > nums[middle + 1])) {
                return middle;
            } else {
                right = middle;
            }
        }

        return nums.front() > nums.back() ? 0 : n - 1;
    }
};

// Since we only need to find any peak, we use a closed interval [left, right]
// to simplify boundary handling and avoid extra edge-case checks.
class Solution {
public:
    int findPeakElement(const vector<int> &nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] < nums[middle + 1]) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        return left;
    }
};