LeetCode: Find Peak Element

Native solution with Linear Scan

The naive solution is scan the array, check whether a element is peak.

Time complexity: $O(N)$.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        for(int i=0; i < nums.size(); i++) {
            int left = i - 1 >= 0 ? nums[i-1] : INT_MIN;
            int right = i + 1 < nums.size() ? nums[i+1] : INT_MIN;
            if(nums[i] > left && nums[i] > right) 
                return i;
        }
        return -1;
    }
};

Because we can return any peak, so there are 3 cases:

arr[0] is peak

arr[arr.size()-1] is peak

peak is in the range of 1...arr.size()-2

file:img/CAPTURE-2020_02_07_find-peak-element.org_20200207_174500.png

In this case, we just need to find the first index, which meets the condition of arr[index] > arr[index + 1]. So we can make the code more simpler:

class Solution {
public:
  int findPeakElement(vector<int>& nums) {
    for(int i=0; i < nums.size() - 1; i++) {
      if(nums[i] > nums[i+1])
        return i;
    }
    return nums.size() - 1;
  }
};

Approach with binary search

Using recursive binary search, the time complexity is $O(logN)$.

class Solution {
public:
  int binary_search(vector<int>& nums, int left, int right) {
    if(left == right) return left;
    int mid = (left + right) / 2;
    if(nums[mid] > nums[mid+1])
      return binary_search(nums, left, mid);
    else
      return binary_search(nums, mid+1, right);
  }

  int findPeakElement(vector<int>& nums) {
    return binary_search(nums, 0, nums.size()-1);
  }
};

Join my Email List for more insights, It's Free!😋

← LeetCode: Maximum Subarray LeetCode: Majority Element →