Peak element

Intuition

Binary search. A peak exists where arr[mid] > arr[mid-1] and arr[mid+1]. If arr[mid] < arr[mid+1]: peak is on right. Else: peak is on left or at mid.

Algorithm

1lo=0, hi=n-1.
2If arr[mid] < arr[mid+1]: lo=mid+1 (ascending, peak on right).
3Else: hi=mid (peak at mid or left).
4Return lo.

Common Pitfalls

•Assume arr[-1]=arr[n]=-infinity. A peak always exists. Binary search converges to a peak.

Peak element.java

Java

// Approach: Binary search. If arr[mid] < arr[mid+1], peak is on right; else peak is on left or at mid.
// Time: O(log n) Space: O(1)
class Solution {

    public int peakElement(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] > arr[mid + 1])
                high = mid;
            else
                low = mid + 1;
        }

        return low;
    }
}

Was this solution helpful?