Find Peak Element

162.Find Peak Element

Array

Binary Search

Problem Statement:

A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element, and return its index. If multiple peaks exist, return any of them. Array is guaranteed to have at least one peak.

Example:

Input:

nums = [1,2,1,3,5,6,4]

→

Output:

5

Index 5 is a peak element because 6 is greater than both neighbors

Algorithm:

1. Check edge cases (length 1 and endpoints)
2. Use binary search on remaining elements
3. Compare mid with neighbors
4. Move towards higher neighbor

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

public int findPeakElement(int[] nums) {
    // Handle single element case
    if (nums.length == 1) return 0;
    
    int n = nums.length;
    
    // Check if first or last element is peak
    if (nums[0] > nums[1]) return 0;
    if (nums[n-1] > nums[n-2]) return n-1;
    
    // Binary search on remaining elements
    int low = 1;
    int high = n - 2;
    
    while (low <= high) {
        int mid = low + (high - low)/2;
        
        // Found peak element
        if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])
            return mid;
        // Go towards higher neighbor
        else if (nums[mid] < nums[mid-1])
            high = mid - 1;
        else
            low = mid + 1;
    }
    
    return -1;  // Should never reach here
}

Python Solution:

def findPeakElement(self, nums: List[int]) -> int:
    # Handle single element case
    if len(nums) == 1:
        return 0
        
    n = len(nums)
    
    # Check if first or last element is peak
    if nums[0] > nums[1]:
        return 0
    if nums[n-1] > nums[n-2]:
        return n-1
        
    # Binary search on remaining elements
    low = 1
    high = n - 2
    
    while low <= high:
        mid = low + (high - low) // 2
        
        # Found peak element
        if nums[mid] > nums[mid + 1] and nums[mid] > nums[mid - 1]:
            return mid
        # Go towards higher neighbor
        elif nums[mid] < nums[mid-1]:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1  # Should never reach here

C++ Solution:

int findPeakElement(vector<int>& nums) {
    // Handle single element case
    if (nums.size() == 1) return 0;
    
    int n = nums.size();
    
    // Check if first or last element is peak
    if (nums[0] > nums[1]) return 0;
    if (nums[n-1] > nums[n-2]) return n-1;
    
    // Binary search on remaining elements
    int low = 1;
    int high = n - 2;
    
    while (low <= high) {
        int mid = low + (high - low)/2;
        
        // Found peak element
        if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])
            return mid;
        // Go towards higher neighbor
        else if (nums[mid] < nums[mid-1])
            high = mid - 1;
        else
            low = mid + 1;
    }
    
    return -1;  // Should never reach here
}