Find Peak Element LeetCode 162

   November 1, 2022

Hello everyone, in this article, we will discuss the famous problem of binary search: Find peek element leetcode (https://leetcode.com/problems/find-peak-element/). We will see the problem explanation, solution approaches, and C++ and python code. This is a leetcode medium-level problem.

Problem Explanation to Find Peak Element leetcode

This problem is very straightforward, we have to find peak element in the given array, and if there is more than one peak element we can return any one. 

Let’s first what a peak element is.

The peak element in an array is an element greater than its adjacent elements.

Find Peak Element LeetCode 162 problem array

Here, 5 is the peak element because it is bigger than its adjacent elements. If the element is an endpoint element, we only have to compare it with only with one adjacent element.

Find Peak Element Find Peak Element LeetCode 162 Hello everyone, in this article, we will discuss the famous problem of binary search: Find peek element leetcode (https://leetcode.com/problems/find-peak-element/). We will see the problem explanation, solution approaches, and C++ and python code. This is a leetcode medium-level problem.

In the above example, there is no peak element.

According to the problem statement, we will always have a solution.

Solution Approaches to leetcode 162

In this article, we will see two approaches to the question

  1. O(n) Approach
  2. O(logn) Approach

1. O(n) Approach to Find Peak Element in LeetCode problem:

In this approach, we compare each element with its adjacent elements and if it is a peak element we will return the element. In this approach, we also have to take care of endpoint elements separately.

We will have two corner cases:

  1. For 1st element
  2. For the last element

For these corner cases, we have to check separately.

C++ Code:

int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 0;
        if(n == 2)return nums[0] > nums[1] ? 0 : 1;
       
        for(int i = 1; i < n-1; i++)
            if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
       
        if(nums[0] > nums[1]) return 0;
        else if(nums[n-1] > nums[n-2]) return n-1;
        return -1;
}

Python Code:

def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if (i == 0 or nums[i-1] < nums[i]) and (i == n-1 or nums[i] > nums[i+1]):  # Found peak
                return i
        return -1

2. O(logn) Approach to Find Peak Element in LeetCode problem:

This approach simply uses binary search, there’s one small trick.

We will implement binary search as we use low and high variables to find the mid.

After finding the mid, we will compare the mid element with both its adjacent elements if the mid element is not the peak element,

We shift towards the higher because there are more chances we will find our peak element towards the higher element.

C++ code:

int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int low = 0, high = n-1;
       
        if(n==1)
            return 0;
        while(low<=high)
        {
            int mid = low + (high-low)/2;
            int prev = (mid+n-1)%n;
            int next = (mid+1)%n;
           
           
            if(mid>0 && mid<n-1)
            {
                    if(nums[mid] > nums[next] && nums[mid] > nums[prev])
                {
                    int res = nums[mid];
                    return mid;
                }
 
 
                else if(nums[next]>nums[mid])
                {
                    low = mid+1;
                }
 
                else
                {
                    high = mid-1;
                }
            }
           
            else if(mid ==0)
            {
                if (nums[0]>nums[1])
                    return 0;
                else
                    return 1;
            }
           
            else{
                if (nums[n-1]>nums[n-2])
                    return n-1;
                else
                    return n-2;
            }
        }
       
        return -1;
}

Python code:

def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if (mid == 0 or nums[mid-1] < nums[mid]) and (mid == n-1 or nums[mid] > nums[mid+1]):  # Found peak
                return mid
            if mid == 0 or nums[mid-1] < nums[mid]:  # Find peak on the right
                left = mid + 1
            else:  # Find peak on the left
                right = mid - 1
        return -1
Best 100+ Python Projects with source code

Also Read:

Share:

Author: Ayush Purawr