Coder's Cat

LeetCode: Find Peak Element

2020-02-07

Challenge Description

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

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

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

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

  • 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;
    }
    };

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);
}
};