Find the Local Minima in an Array

Title: Find the Local Minima in an Array

Understanding the Problem

A local minima in an array is an element that is smaller than or equal to both of its immediate neighbors. For the first element, only the element to its right counts as a neighbor; for the last element, only the element to its left counts. In this guide you will learn how to find a local minima in O(log n) time using a binary search style approach, instead of the obvious O(n) linear scan.

This problem is a favorite in interviews because it looks like a simple scan but hides a clever divide and conquer trick. By the end of this post you will have a full Java program, a step by step trace of the algorithm, worked examples, common mistakes to avoid, edge cases to test, and a set of interview follow up questions to push your understanding further.

Approach to Find the Local Minima

The key insight is that any array has at least one local minima, guaranteed by its boundaries. If the array is sorted in increasing order, index 0 is a local minima. If it is sorted in decreasing order, the last index is a local minima. Otherwise, somewhere the values must dip and then rise again, and that dip is a local minima. We can exploit this with binary search:

1. Set low = 0 and high = n - 1.
2. While low <= high, compute mid = low + (high - low) / 2.
3. Check whether arr[mid] is a local minima by comparing it against arr[mid - 1] (if it exists) and arr[mid + 1] (if it exists).
4. If both neighbor checks pass, mid is a valid local minima; return it.
5. If the left neighbor is smaller than arr[mid], a local minima must exist in the left half, so set high = mid - 1.
6. Otherwise, a local minima must exist in the right half, so set low = mid + 1.
7. Repeat until a local minima is returned.

Each iteration discards roughly half of the remaining window while still guaranteeing that a local minima exists inside the half that is kept, which is exactly what makes the O(log n) bound correct.

Java Program

Here is a complete, compilable Java program that implements the binary search approach described above.

public class LocalMinimaFinder {

    public static int findLocalMinima(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            throw new IllegalArgumentException("Array must contain at least one element");
        }
        int low = 0;
        int high = n - 1;

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

            boolean leftOk = (mid == 0) || (arr[mid] <= arr[mid - 1]);
            boolean rightOk = (mid == n - 1) || (arr[mid] <= arr[mid + 1]);

            if (leftOk && rightOk) {
                return mid;
            } else if (mid > 0 && arr[mid - 1] < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 14, 5, 7, 4};
        int index = findLocalMinima(arr);
        if (index != -1) {
            System.out.println("Local minima found at index " + index + " -> value " + arr[index]);
        } else {
            System.out.println("No local minima found");
        }
    }
}

Explanation of the Program

The method findLocalMinima takes the array arr and runs the binary search described earlier. Here is what each part does:

• low and high track the current search window, starting at the full array.
• mid is recomputed every iteration as the midpoint of the current window.
• leftOk is true when mid is the first index, or when arr[mid] is not greater than its left neighbor.
• rightOk is true when mid is the last index, or when arr[mid] is not greater than its right neighbor.
• When both flags are true, arr[mid] satisfies the local minima definition, so the method returns mid immediately.
• When leftOk fails, the left neighbor is strictly smaller, which proves a local minima exists somewhere in [low, mid - 1], so the window shrinks to that half.
• Otherwise, the right half is guaranteed to contain a local minima, so the window shrinks to [mid + 1, high].

The main method simply calls findLocalMinima on a sample array and prints the index and value that were found.

Step-by-Step Trace

Let's trace the algorithm on the array {10, 8, 5, 12, 3, 9, 6}, where the target is to land on a valid local minima index.

At the end of each iteration, the window [low, high] still contains at least one valid local minima, which is exactly why shrinking the window in either direction never loses the answer.

Examples

Example 1: Minima at the First Index

When the array is strictly increasing, the first element is always a local minima because it only needs to be smaller than or equal to the element on its right.

int[] arr = {1, 5, 8, 9, 10};
int index = findLocalMinima(arr);
// index -> 0, value -> 1

Example 2: Minima at the Last Index

When the array is strictly decreasing, the same reasoning applies in reverse, and the last element becomes the local minima.

int[] arr = {20, 15, 10, 6, 2};
int index = findLocalMinima(arr);
// index -> 4, value -> 2 (minima sits at the last index)

Example 3: Multiple Local Minima

An array can contain more than one local minima. The algorithm only guarantees that it will return a valid one, not necessarily the smallest value or the first one in reading order.

int[] arr = {4, 1, 7, 2, 9, 3, 10};
int index = findLocalMinima(arr);
// index -> 3, value -> 2 (one of three valid local minima in this array)

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this exact binary search for a local minima.

• Assuming the result is the global minimum - the algorithm only promises a local minima, not the smallest value in the array. On {4, 1, 7, 2, 9, 3, 10} it may return index 3 with value 2 even though the global minimum 1 sits at index 1. Do not reuse this code where the true minimum is required; use a linear scan for that instead.
• Forgetting the boundary checks - comparing arr[mid - 1] or arr[mid + 1] without first checking mid == 0 or mid == n - 1 throws ArrayIndexOutOfBoundsException at the edges of the array. Always guard with the boundary condition before touching a neighbor.
• Using strict inequality in the neighbor check - writing arr[mid] < arr[mid - 1] instead of arr[mid] <= arr[mid - 1] rejects valid plateaus where a minima ties with its neighbor, which can make the loop run past a correct answer. Keep the comparisons inclusive, as in leftOk and rightOk above.
• Picking the wrong half when neither side is immediately valid - moving right when the left neighbor is actually the smaller one skips over the half that is guaranteed to contain a minima, which can make the method return -1 for an array that clearly has one. Always move toward the side whose neighbor is strictly smaller than arr[mid].

Edge Cases to Test

Walk through these input shapes before calling the implementation finished.

• Single-element array
• Two-element array
• Strictly increasing array
• Strictly decreasing array
• Minima at index 0
• Minima at the last index
• Multiple local minima present
• Integer.MIN_VALUE or Integer.MAX_VALUE present

Additional Considerations

The binary search approach runs in O(log n) time since the search window is halved on every iteration, and it uses only O(1) extra space because low, high, and mid are the only variables tracked. This is a clear improvement over the naive O(n) linear scan that checks every index against its neighbors, although the linear scan has its own advantage: it is the only way to find every local minima rather than just one.

The single-element edge case matters for a subtle reason: with n == 1, both mid == 0 and mid == n - 1 are true at the same time, so leftOk and rightOk are both trivially true and the only element is immediately returned. The Integer.MIN_VALUE and Integer.MAX_VALUE case matters because the comparisons in leftOk and rightOk rely only on <=, which never overflows the way arithmetic such as subtraction between two extreme values would.

Interview Follow-up Questions

Once you can explain the base solution, expect an interviewer to push further with questions like these.

• What if adjacent elements can be equal across a long plateau? - the direction choice in the binary search becomes ambiguous when arr[mid - 1] == arr[mid], so fall back to a linear scan, or only apply binary search once you have confirmed no two adjacent elements are equal.
• What if you need every local minima instead of just one? - binary search cannot enumerate all of them in better than linear time, so switch to a single O(n) pass comparing each element to both neighbors.
• What if the array is actually a 2D grid and you need a local minima in both dimensions? - generalize the same idea by repeatedly moving from the current cell toward whichever of its up to four neighbors holds a smaller value, which still converges in roughly logarithmic steps per dimension.
• What if the array is too large to fit in memory and arrives as a stream? - binary search needs random access to arbitrary indices, which a stream does not offer, so you would need to fall back to a sequential scan that tracks the previous and current values and detects a dip as it passes.

Conclusion

Finding a local minima is a great example of how a boundary guarantee lets you turn an apparent O(n) scan into an O(log n) binary search. The core trick is always the same: at every step, prove that the half you are discarding cannot possibly contain the answer you need.

Try adapting the program above to return all local minima, or to work on a 2D grid, to make sure you understand why the binary search invariant holds. You can learn more about array-based algorithms like this one in our Arrays category on Daily Java Concept.