Find the Peak Element in an Array

Title: Find the Peak Element in an Array

A peak element is one that is strictly greater than its immediate neighbors. For the first element only the next element counts as a neighbor, and for the last element only the previous one does. In this guide, you’ll learn how to find a peak element in a Java array efficiently using binary search, without scanning the whole array every time.

We’ll walk through the problem, build the algorithm step by step, trace it on a concrete input, and cover the mistakes, edge cases, and interview follow-ups that come up around this problem.

Understanding the Problem

You are given an array of integers nums. An index i is a peak if nums[i] is greater than nums[i - 1] (when i is not the first index) and greater than nums[i + 1] (when i is not the last index). The array may contain more than one peak, and the task is simply to return the index of any one of them.

For example, given the input:

int[] numbers = {1, 2, 3, 1};

index 2 is a valid answer, because the value 3 is greater than both of its neighbors.

A simple linear scan finds a peak in O(n) time, but this problem is far more interesting when solved in O(log n) time using binary search, which is what the rest of this guide focuses on.

Approach: Binary Search Toward the Rising Slope

The key insight is that if nums[mid] is smaller than its right neighbor, the array is still rising at mid, so a peak must exist somewhere to the right. If nums[mid] is greater than or equal to its right neighbor, a peak must exist at mid or somewhere to its left. This lets us discard half the array on every step.

Here are the steps:

1. Handle the trivial case: if nums is null or empty, throw an exception.
2. Initialize low = 0 and high = nums.length - 1.
3. While low < high, compute mid = low + (high - low) / 2.
4. If nums[mid] < nums[mid + 1], the slope is still rising, so set low = mid + 1.
5. Otherwise, the slope is falling or flat at mid, so set high = mid (keep mid in the search space).
6. When low equals high, that index is a peak; return it.

Java Program to Find the Peak Element in an Array

Here is the complete, runnable Java program implementing the binary search approach:

public class FindPeakElement {

    public static int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }

        int low = 0;
        int high = nums.length - 1;

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

            if (nums[mid] < nums[mid + 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 1};
        int peakIndex = findPeakElement(numbers);

        System.out.println("Peak index: " + peakIndex);
        System.out.println("Peak value: " + numbers[peakIndex]);
    }
}

Explanation of the Program

The findPeakElement method first validates the input, since an empty array has no peak to return. It then sets low and high to the first and last valid indices.

Inside the while loop, mid is computed using low + (high - low) / 2 rather than (low + high) / 2, which avoids integer overflow on very large arrays. The method then compares nums[mid] to its right neighbor, nums[mid + 1], which is always a valid index because mid < high inside the loop.

If the array is still climbing at mid, the peak cannot be at or before mid, so the search moves to low = mid + 1. Otherwise the peak is at mid or to its left, so high is set to mid itself, keeping it in play. The loop ends when low and high converge, and that shared index is returned.

Step-by-Step Trace

Let’s trace the algorithm on the input [1, 2, 4, 3, 5, 6, 2], which has seven elements at indices 0 through 6. The expected output is index 5, since nums[5] = 6 is greater than both nums[4] = 5 and nums[6] = 2.

At the end of each iteration, the invariant holds: the subarray nums[low..high] still contains at least one peak. When low and high meet at index 5, the loop stops and 5 is returned.

Examples

Example 1: A Single Interior Peak

An array with exactly one element that is greater than both of its neighbors.

int[] numbers = {1, 2, 3, 1};
int peakIndex = findPeakElement(numbers);
System.out.println(peakIndex);
// Output: 2 (value 3 is greater than both neighbors)

Example 2: Multiple Valid Peaks

An array with more than one peak. Binary search is only required to return one of them, and which one it returns depends on which half it narrows into first.

int[] numbers = {1, 2, 1, 3, 5, 6, 4};
int peakIndex = findPeakElement(numbers);
System.out.println(peakIndex);
// Output: 1 or 5 (both index 1, value 2, and index 5, value 6, are valid peaks)

Example 3: Single-Element Array

With only one element, there are no neighbors to compare against, so that element is a peak by definition.

int[] numbers = {7};
int peakIndex = findPeakElement(numbers);
System.out.println(peakIndex);
// Output: 0 (a single element has no neighbors, so it is a peak by default)

Common Mistakes to Avoid

This algorithm is short, but a few specific missteps are easy to make. Watch for these:

• Assuming the peak is the global maximum – the method returns any valid peak, not necessarily the largest value in the array, so on an input like [1, 3, 1, 5, 1] it may return index 1 instead of index 3. If you specifically need the largest value, scan linearly and track the maximum instead.
• Setting high = mid – 1 instead of high = mid – this excludes mid from the search space even though mid itself might be the peak, which can cause the algorithm to converge on the wrong index or never terminate. Always set high = mid when the slope is falling or flat.
• Comparing nums[mid] to nums[mid – 1] instead of nums[mid + 1] – this throws an ArrayIndexOutOfBoundsException whenever mid is 0. The comparison must always look at the right neighbor, nums[mid + 1], which is always in bounds because the loop guarantees mid < high.
• Skipping the null or empty check – calling nums.length on a null array throws a NullPointerException, and an empty array has no index to return. Validate the input before touching low and high.
• Forgetting the edge comparison in a linear scan – if you instead write a linear version, comparing nums[i] only to nums[i - 1] misses the case where index 0 or the last index is the peak. Special-case both ends so each is compared only to its single neighbor.

Edge Cases to Test

Before you call the solution complete, walk through these inputs:

• Empty array
• Single-element array
• Strictly increasing array (peak at the last index)
• Strictly decreasing array (peak at the first index)
• Peak located at index 0
• Peak located at the last index
• Multiple peaks present
• Null array reference

Additional Considerations

The binary search solution runs in O(log n) time, since each iteration discards roughly half of the remaining search space. It uses O(1) auxiliary memory, because only a handful of index variables are needed regardless of the array’s size.

A linear scan achieves the same result in O(n) time and O(1) space, and it is simpler to write. The trade-off is speed on large arrays: binary search finds a peak in a million-element array in around twenty comparisons, while a linear scan may need close to a million.

Keep in mind that this problem, as defined here, only guarantees finding a peak, not the largest value in the array. If the problem statement guarantees nums[i] != nums[i + 1] for all adjacent pairs, the binary search approach is guaranteed to terminate on a valid peak; plateaus of equal adjacent values would otherwise need a different definition of what counts as a peak.

Interview Follow-up Questions

This problem is a common jumping-off point for several follow-up questions. Expect to be asked some of the following:

• What if you need to find all peak elements, not just one? – a single binary search cannot do this; instead scan linearly, checking each index against its neighbors and collecting every match, which takes O(n) time.
• What if the array can contain plateaus of equal adjacent values? – redefine a peak using >= instead of strictly >, or skip over runs of equal values until you reach the next distinct element before comparing.
• What if the input is a 2D grid and you need a peak element in the grid? – binary search on columns, and at each column move toward whichever neighboring column has the larger value in the same row’s maximum, which gives an O(n log m) divide-and-conquer solution.
• What if the input arrives as a stream and you cannot look backward? – true binary search is impossible without random access; instead keep a small sliding window of the last few values to detect the moment the sequence starts descending, which costs O(n) time overall.
• What if you must return the true global maximum under a strict O(1) extra memory limit? – binary search alone cannot guarantee this on arrays with multiple peaks, so you need a full linear scan that tracks the maximum value and its index as it goes, which is O(n) time and O(1) space.

Conclusion

Finding a peak element is a great example of how a problem that looks like it needs a full scan can often be solved faster once you spot the right invariant, in this case that a rising slope always leads toward a peak. The binary search version is the one interviewers expect once they hear you mention the O(n) linear scan first.

Try adapting the program to return the actual peak value instead of its index, or to find all peaks in a single linear pass. Both variations reinforce the same core idea and prepare you for the follow-up questions above.

You can learn more about array algorithms here: Arrays.