Find the Local Maxima in an Array

Title: Find the Local Maxima in an Array

A local maximum is an element that is strictly greater than its immediate neighbors. Unlike searching for a single peak, this problem asks you to find every such element in the array, not just one of them. In this guide, you’ll learn how to scan a Java array once and collect every local maximum in O(n) time.

We’ll define the problem precisely, 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 local maximum 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 first and last elements are only compared against their single neighbor, so either one can qualify as a local maximum on its own.

For example, given the input:

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

indices 1, 3, and 5 are all local maxima, because the values 3, 4, and 5 are each greater than both of their neighbors. Notice that the array can have several local maxima at once; the task is to return all of them, not just the largest.

This is a different goal from finding a single peak element with binary search. Because every index must be checked, a full linear scan is unavoidable, which is exactly what makes O(n) the best possible time complexity here.

Approach: Single Pass with Boundary-Aware Comparisons

The core idea is to walk the array once and, at each index, decide independently whether it beats its left neighbor and whether it beats its right neighbor. For the first index there is no left neighbor to beat, and for the last index there is no right neighbor to beat, so those checks are simply treated as automatically satisfied.

Here are the steps:

1. Handle the trivial case: if nums is null or empty, throw an exception.
2. Create an empty list maxima to hold the qualifying indices, and store n = nums.length.
3. Iterate i from 0 to n - 1.
4. Compute greaterThanLeft: true when i == 0, otherwise nums[i] > nums[i - 1].
5. Compute greaterThanRight: true when i == n - 1, otherwise nums[i] > nums[i + 1].
6. If both flags are true, add i to maxima.
7. After the loop finishes, return maxima.

Java Program to Find the Local Maxima in an Array

Here is the complete, runnable Java program implementing the single-pass approach:

import java.util.ArrayList;
import java.util.List;

public class FindLocalMaxima {

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

        List<Integer> maxima = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            boolean greaterThanLeft = (i == 0) || nums[i] > nums[i - 1];
            boolean greaterThanRight = (i == n - 1) || nums[i] > nums[i + 1];

            if (greaterThanLeft && greaterThanRight) {
                maxima.add(i);
            }
        }

        return maxima;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 3, 2, 4, 1, 5, 2};
        List<Integer> maximaIndices = findLocalMaxima(numbers);

        System.out.println("Local maxima indices: " + maximaIndices);
        for (int index : maximaIndices) {
            System.out.println("nums[" + index + "] = " + numbers[index]);
        }
    }
}

Explanation of the Program

The findLocalMaxima method first validates the input, since an empty array has no elements to examine. It then creates an empty ArrayList called maxima to collect the qualifying indices as it scans.

Inside the for loop, greaterThanLeft and greaterThanRight are computed as boolean flags rather than as separate if branches for the endpoints. The expression (i == 0) || nums[i] > nums[i - 1] short-circuits before touching nums[i - 1] whenever i is 0, which avoids an ArrayIndexOutOfBoundsException without needing a separate code path for the first element.

The same pattern applies to greaterThanRight at the last index. When both flags are true, nums[i] beats every neighbor it actually has, so i is appended to maxima. The loop never stops early; it always visits every index, because any of them could be a local maximum.

Step-by-Step Trace

Let’s trace the algorithm on the input [5, 1, 6, 2, 8, 3], which has six elements at indices 0 through 5. The expected output is [0, 2, 4], since nums[0] = 5, nums[2] = 6, and nums[4] = 8 each beat every neighbor they have.

At the end of index i, maxima holds every index in nums[0..i] that is strictly greater than each neighbor it actually has.

Examples

Example 1: Multiple Local Maxima

An array with three separate local maxima, none of which is the global maximum of the array by itself; each is simply larger than its own neighbors.

int[] numbers = {1, 3, 2, 4, 1, 5, 2};
List<Integer> maximaIndices = findLocalMaxima(numbers);
System.out.println(maximaIndices);
// Output: [1, 3, 5] (values 3, 4, and 5 are each greater than both neighbors)

Example 2: Strictly Increasing Array

When the array is strictly increasing, every interior element has a larger right neighbor, so only the last index, which has no right neighbor to lose to, qualifies.

int[] numbers = {1, 2, 3, 4, 5};
List<Integer> maximaIndices = findLocalMaxima(numbers);
System.out.println(maximaIndices);
// Output: [4] (a strictly increasing array has only the last element as a local maximum)

Example 3: Single-Element Array

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

int[] numbers = {9};
List<Integer> maximaIndices = findLocalMaxima(numbers);
System.out.println(maximaIndices);
// Output: [0] (a single element has no neighbors, so it is a local maximum by default)

Common Mistakes to Avoid

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

• Checking only one neighbor – comparing nums[i] only to nums[i - 1] wrongly marks index 1 as a local maximum on an input like [1, 5, 6, 2], even though nums[2] = 6 is larger. Always require the element to beat both neighbors it has.
• Forgetting the endpoint special case – comparing nums[0] to nums[-1] or nums[n - 1] to nums[n] throws an ArrayIndexOutOfBoundsException. Treat the missing neighbor as automatically satisfied instead of indexing past the array.
• Using >= instead of > – this treats equal adjacent values as local maxima, so a plateau like [3, 3, 2] incorrectly reports both 3s as maxima. Use strict > unless the problem statement explicitly asks for plateaus to count.
• Stopping after the first match – returning as soon as one local maximum is found misses every later one, since this problem asks for all of them, not just any single peak. Keep scanning the full array and append every match to the result list.
• Dropping endpoints from the loop bounds – looping only from i = 1 to i = n - 2 to avoid out-of-bounds access silently skips valid local maxima at index 0 or the last index. Keep the loop over the full range and let the boundary-aware flags handle the edges.

Edge Cases to Test

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

• Empty array
• Single-element array
• All identical elements (plateau)
• Strictly increasing array
• Strictly decreasing array
• Local maximum at index 0
• Local maximum at the last index
• Null array reference

Additional Considerations

The single-pass solution runs in O(n) time, since every index is visited exactly once and each visit does a constant amount of work. It uses O(1) auxiliary memory beyond the output, because the two boolean flags are the only extra state kept per iteration.

The output list itself can grow up to roughly n / 2 entries, which happens on a strictly alternating array like [1, 5, 2, 6, 3, 7] where every other element is a local maximum. That is the expected worst case for the result size, not a sign of a bug.

Finding a single peak is a related but different problem that can be solved in O(log n) time with binary search, because it only needs to return one valid answer. This problem needs every local maximum, so it cannot skip over any part of the array and must stay at O(n).

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 only need to find any one local maximum, not all of them? – binary search toward the rising slope solves that variant in O(log n), the same idea used for the peak element problem.
• What if the array can contain plateaus of equal adjacent values? – decide whether a flat run should count as a single maximum region, then skip over the run of equal values and compare only against the elements bounding it.
• What if the array is circular, so the first and last elements are neighbors? – drop the endpoint special cases entirely and compare index 0 against index n – 1 directly using modular indexing.
• What if the array arrives as a stream and you cannot look ahead? – buffer the previous two values and only decide on the middle one once the next value is known, which detects each maximum exactly one step behind the stream.
• What if you need only the top K local maxima by value, not all of them? – collect every local maximum in O(n) first, then use a min-heap of size K to keep the K largest, which adds O(n log K) on top of the scan.

Conclusion

Finding every local maximum in an array comes down to one clean idea: check each element against whichever neighbors it actually has, and let the missing neighbor at either end count as an automatic win. That single rule handles the interior elements and both endpoints without any special-cased branches.

Try adapting the program to return the local maximum values instead of their indices, or to find the local minima using the same pattern with the comparison flipped. 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.