Solution For Find Peak Element

Problem Statement:

A peak element in an integer array is an element that is strictly greater than its neighbours. Given an 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] = -∞.

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: 1 or 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.

Solution:

The problem can be solved by applying Binary Search Algorithm. The idea behind applying Binary Search Algorithm is to look for the middle element and compare it with its neighbours. If it is a peak element, then we return the index of the middle element otherwise we move towards the side which has greater number in comparison with neighbours.

Let’s look at the following scenarios:

1. When the middle element is greater than its neighbours, then we return the index of the middle element.
2. When the left neighbour of middle element is greater than the middle element, then we move towards the left side, as there can be more elements on left side which can be the peak element.
3. When the right neighbour of middle element is greater than the middle element, we move towards the right side, as there can be more elements on right side which can be the peak element.

Algorithm:

1. Define Binary Search Function with the input parameter, an integer array nums.
2. Initialize the variables, start = 0 and end = nums.size()-1.
3. Apply the while loop and check whether start<=end.
4. Calculate the value of the mid element using the formula mid = start + (end-start)/2.
5. Check the three conditions as discussed above.
6. If the mid element is greater than its neighbours, return the mid element index.
7. If the left neighbour of the mid element is greater than mid element, we update the value of end = mid -1.
8. If the right neighbour of the mid element greater than mid element, we update the value of start = mid+1.
9. We return -1 if we are not able to find the peak element.

Pseudo Code:

“`
int findPeakElement(vector& nums) {
int start = 0;
int end = nums.size() – 1;

while (start <= end) {
    int mid = start + (end - start) / 2;
    if ((mid == 0 || nums[mid] > nums[mid - 1]) && (mid == nums.size() - 1 || nums[mid] > nums[mid + 1])) {
        return mid;
    }
    else if (mid > 0 && nums[mid - 1] > nums[mid]) {
        end = mid - 1;
    }
    else {
        start = mid + 1;
    }
}

return -1;

}
“`

Time Complexity:

The time complexity of the above algorithm is O(logn) as we are applying Binary Search Algorithm.

Space Complexity:

The space complexity is O(1), as we are not using any extra space.

Conclusion:

In conclusion, the above problem can be solved by applying Binary Search Algorithm. We have to check three cases and return the mid element index, if it satisfies any of those three cases. If the peak element is not found, then we return -1. The time complexity is O(logn) and the space complexity is O(1).

Step by Step Implementation For Find Peak Element

public int findPeakElement(int[] nums) {
        // start searching from the middle element
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // if the middle element is less than the element to its right
            // then there must be a peak element on the right side
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            // if the middle element is greater than the element to its right
            // then there must be a peak element on the left side
            } else {
                right = mid;
            }
        }
        // 'left' will be pointing to the peak element when the loop ends
        return left;
    }

# Solution:

def findPeakElement(nums):
    
    # Base case:
    if len(nums) == 1:
        return 0
    
    # Iterate through the array:
    for i in range(len(nums)):
        
        # Check if the current element is greater than its neighbors:
        if i == 0:
            if nums[i] > nums[i+1]:
                return i
        elif i == len(nums)-1:
            if nums[i] > nums[i-1]:
                return i
        else:
            if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
                return i

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    // Set the left and right pointers
    let left = 0, right = nums.length - 1;
    
    // While the left pointer is less than the right pointer
    while(left < right) {
        // Get the middle index
        let mid = Math.floor((left + right) / 2);
        
        // If the element at the middle index is less than the element to its right
        if(nums[mid] < nums[mid + 1]) {
            // The peak element is to the right of the middle index
            // Set the left pointer to be the middle index + 1
            left = mid + 1;
        // Otherwise, if the element at the middle index is greater than the element to its right    
        } else {
            // The peak element is to the left of the middle index
            // Set the right pointer to be the middle index
            right = mid;
        }
    }
    
    // At this point, the left and right pointers should be equal
    // This is the index of the peak element
    return left;
};

There are multiple ways to solve this problem. One approach is to use a binary search algorithm to find the element that is greater than its neighbors.

int findPeakElement(vector& nums) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = (left + right) / 2; if (nums[mid] > nums[mid + 1]) right = mid; else left = mid + 1; } return left; }

class Solution { 
    public int FindPeakElement(int[] nums) {
        //check for empty or null array 
        if (nums == null || nums.Length == 0) { 
            return -1; 
        } 
          
        //binary search for the peak element 
        int start = 0; 
        int end = nums.Length - 1; 
        while (start < end) { 
            int mid = (start + end) / 2; 
            if (nums[mid] < nums[mid + 1]) { 
                start = mid + 1; 
            } 
            else { 
                end = mid; 
            } 
        } 
          
        //return the index of the peak element 
        return start; 
    } 
}