Java Programs›Arrays›Find Local Minimum in an Array

Find Local Minimum in an Array in Java

intermediate· Arrays · Array

Problem

A local minimum is an element that is strictly smaller than the elements immediately next to it — an edge element only needs to beat its single neighbor.

Given an array of integers, find any one local minimum it contains.

Input

[9, 6, 3, 14, 5, 7, 4]

Output

Local minimum: 3

Java Program

Java

public class LocalMinimum {
    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 14, 5, 7, 4};
        int localMin = arr[0];

        for (int i = 0; i < arr.length; i++) {
            boolean leftOk = (i == 0) || arr[i] < arr[i - 1]; // no left neighbor to beat at index 0
            boolean rightOk = (i == arr.length - 1) || arr[i] < arr[i + 1]; // no right neighbor at the last index
            if (leftOk && rightOk) {
                localMin = arr[i];
                break; // found a local minimum, no need to keep scanning
            }
        }

        System.out.println("Local minimum: " + localMin);
    }
}

▶ Run Code

Output

Local minimum: 3

Core Logic

Checking each position against both of its neighbors, treating the array's edges as having only one neighbor to satisfy, finds a local minimum in a single left-to-right scan — the mirror image of finding a peak.

How It Works

1leftOk is true automatically at index 0 (no left neighbor to beat), otherwise it checks arr[i] < arr[i - 1].
2rightOk is true automatically at the last index (no right neighbor to beat), otherwise it checks arr[i] < arr[i + 1].
3A position that satisfies both conditions is a local minimum, and the loop breaks as soon as one is found.
4The array can have multiple valid local minima — this returns whichever one the left-to-right scan reaches first.

For [9, 6, 3, 14, 5, 7, 4], index 2 (value 3) beats both neighbors — 6 on the left and 14 on the right — so it's reported as the local minimum.

💡

Key Point: 'A' local minimum, not 'the' local minimum — an array can have several elements that each beat both their neighbors, and any one of them is a correct answer.

Complexity

Time Complexity: O(n)Space Complexity: O(1)

Why: In the worst case every element is checked once before a local minimum is found, and only two boolean flags are kept per position.

Key Concepts

neighbor comparisonboundary conditionsearly exit with break

Approach 2: Binary Search

Java

public class LocalMinimumBinarySearch {
    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 14, 5, 7, 4};
        int left = 0, right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid + 1]) {
                left = mid + 1; // a local minimum exists to the right
            } else {
                right = mid; // a local minimum exists at mid or to the left
            }
        }

        System.out.println("Local minimum: " + arr[left]);
    }
}

▶ Run Code

Output

Local minimum: 4

Core Logic

Comparing the middle element to its right neighbor reveals which half of the array must contain a local minimum — a falling slope means one exists further right, a rising slope means one exists at or before the midpoint.

How It Works

1mid is computed as the midpoint between left and right.
2If arr[mid] > arr[mid + 1], the sequence is still falling at mid, so a local minimum must exist somewhere to the right — left moves past mid.
3Otherwise, the sequence is rising (or mid is itself a local minimum), so a local minimum exists at mid or earlier — right shrinks down to mid.
4The loop ends once left and right converge, and that shared index is guaranteed to be a local minimum.

For [9, 6, 3, 14, 5, 7, 4], this search happens to converge on index 6, reporting 4 — a different local minimum than the linear scan's 3, but an equally valid one.

💡

Key Point: This array has more than one local minimum, and the two algorithms here land on different ones — both are correct, since the problem only ever asks for 'a' local minimum, not a specific one.

Complexity

Time Complexity: O(log n)Space Complexity: O(1)

Why: The search range is cut roughly in half at every step, so the number of comparisons grows logarithmically instead of linearly with the array's length.

Key Concepts

binary searchslope comparisonlogarithmic search

← Previous

Find Least Frequent Element

Find Longest Consecutive Sequence

Related Programs

Arraysbeginner

Average Array Elements

Check Array Is Sorted

Arraysbeginner

Compare Two Arrays