Find Peak Element - Leetcode Solution

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<int>& 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).

1