Find Peak Element LeetCode Solution

Problem Statement

Find Peak Element LeetCode Solution says that – 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.

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.

Constraints:

• 1 <= nums.length <= 1000
• -2³¹ <= nums[i] <= 2³¹ - 1
• nums[i] != nums[i + 1] for all valid i.

ALGORITHM –

IDEA –

• In order to Find Peak elements. First, we will focus on using Binary Search.
• At first, we will find the middle element and will check that if the middle element is greater than the next element(because we have to focus on the peak and here the peak situation is happening)  then we will update the high = mid.
• Else we will check for the condition if the middle is smaller than the next element (no peak situation is happening). So basically we will update the low = mid+1.
• and last we will return to the low.

APPROACH –

• First, we will use Binary search in this question. we will make variable low = 0 and high = length of nums -1.
• Then we will use condition while(low < high) and within the condition, we will find the middle.
• After that, we will check if middle >middle+1 then update the high = mid.
• Else Update the low = mid+1. This process will run until low is greater than or equal to high.
• At last, we will return low. Hence we will Find The Peak Element.

Image of  Solution of Find peak –

class Solution {
    public int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length-1;
        
        while(low < high){
            
            int mid = (low+high)/2;
            if(nums[mid] > nums[mid+1]){
                
                high = mid;
                
                
            }
            else
                low = mid+1;
            
            
        }
        return low;
        
        
    }
}

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        low = 0
        high = len(nums)-1
        while(low < high):
            mid = (low+high)//2
            
            if nums[mid] > nums[mid+1]:
                high = mid
                
            else:
                low = mid+1
                
        return low

Time Complexity: O(LOGN). For using Binary Search.

Space Complexity: O(1). As we have not taken any Extra Space.

SIMILAR QUESTIONS – https://tutorialcup.com/leetcode-solutions/find-a-peak-element-ii-leetcode-solution.htm