Last updated on January 13th, 2025 at 03:11 am

Here, we see a Find Peak Element LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Binary Search

Companies

Google, Microsoft

Level of Question

Medium

Find Peak Element LeetCode Solution

1. Problem Statement

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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Modified Binary Search. This pattern is used when the problem involves searching for a specific element or condition in a sorted or partially sorted array, and the search space can be reduced by dividing it into halves.

3. Code Implementation in Different Languages

3.1 Find Peak Element C++

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

3.2 Find Peak Element Java

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

3.3 Find Peak Element JavaScript

var findPeakElement = function(nums) {
    let left = 0, right = nums.length-1, mid;
    while(left < right) {
        mid = Math.floor((right+left)/2);
        if(nums[mid] > nums[mid+1]) right = mid;
        else left = mid+1;
    }
    return left;
};

3.4 Find Peak Element Python

class Solution(object):
    def findPeakElement(self, nums):
        left = 0
        right = len(nums)-1
        while left < right-1:
            mid = (left+right)/2
            if nums[mid] > nums[mid+1] and nums[mid] > nums[mid-1]:
                return mid
            if nums[mid] < nums[mid+1]:
                left = mid+1
            else:
                right = mid-1
        return left if nums[left] >= nums[right] else right

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(log n)	O(1)
JavaScript	O(log n)	O(1)
Python	O(log n)	O(1)

• The C++ implementation is less efficient (O(n)) compared to the other implementations (O(log n)) because it uses a linear search.
• The Java, JavaScript, and Python implementations are more efficient as they use binary search to reduce the search space logarithmically.
• All implementations have a space complexity of O(1) since they do not use any additional data structures.