Find Peak Element

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.

Constraints:

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

Solution:

Note

• No two elements are adjacent. Therefore one neighbour can either be greater than the other neighbour or it can be lesser; equality is not possible.(V Imppp) this means The graph at mid can either be increasing or decreasing.

More Intuitive

class Solution {
    public int findPeakElement(int[] nums) {
        // If there's only one element, it's the peak by default
        if (nums.length == 1) return 0;
        
        int n = nums.length;
        
        // Check if the first or last element is a peak
        if (nums[0] > nums[1]) return 0;
        if (nums[n - 1] > nums[n - 2]) return n - 1;
        
        // Perform binary search in the remaining array
        int start = 1;
        int end = n - 2;
        
        while (start <= end) {
            int mid = start + (end - start) / 2;
            
            // Check if mid is a peak
            if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) return mid;
            // If mid is less than its previous element, the peak is in the left half
            else if (nums[mid - 1] > nums[mid]) end = mid - 1;
            // If mid is less than its next element, the peak is in the right half
            else start = mid + 1;
        }
        
        // Dummy return, this line should never be reached if input is valid
        return -1;
    }
}

Little less Intuitive but better solution in terms of clarity and less base cases:

• The condition start <= end needs to be carefully managed to avoid infinite loops or incorrect results, hence start < end is used.

class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
 
        while (start < end) {
            int mid = start + (end - start) / 2;
 
            if (nums[mid] < nums[mid + 1]) {
                // If the middle element is less than the next element,
                // then the peak is in the right half (excluding mid)
                start = mid + 1;
            } else {
                // If the middle element is greater than or equal to the next element,
                // then the peak is in the left half (including mid)
                end = mid;
            }
        }
 
        // When start == end, it will point to the peak element
        return start;
    }
}