LeetCode: Find Peak Element

\(\)

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:

  1. arr[0] is peak

CAPTURE-2020_02_07_find-peak-element.org_20200207_174303.png

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

CAPTURE-2020_02_07_find-peak-element.org_20200207_174328.png

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

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);
  }
};
Don't miss out!
Subscribe To Newsletter

Want to be better at coding and CS ?

Programming tutorials

Career advice and tips

......

It's Free!

Invalid email address
Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *