Find the Valley Element in an Array

Title: Find the Valley Element in an Array

In this guide, you’ll learn how to find a valley element in an array of integers. A valley element is a value that is smaller than both of its neighbors, and it turns up often in interview rounds right alongside its twin problem, the peak element.

We’ll walk through a precise definition of the problem, build an efficient O(log n) solution using binary search, trace the algorithm by hand on a concrete array, and then cover the mistakes, edge cases, and follow-up questions that tend to come up when this problem is used in an interview.

Understanding the Problem

Given an array of integers arr, a valley element is any element that is less than or equal to both of its immediate neighbors. For an element at the first or last index, only the single neighbor that exists needs to be checked.

For example, in {9, 4, 2, 7, 1, 8}, both index 2 (2, smaller than 4 and 7) and index 4 (1, smaller than 7 and 8) qualify as valleys. The task only asks for one valid index, not every valley in the array.

It helps to contrast this with the peak element problem. A peak is larger than its neighbors; a valley is smaller. The two problems share the exact same binary search structure, just with the comparison flipped, so mastering one gets you the other for free.

Every array of length 1 or more is guaranteed to contain at least one valley. The boundary elements only need to beat a single neighbor, and this guarantee is exactly what makes a binary search solution possible instead of a plain linear scan.

Approach / Algorithm Steps

The key insight is that you never need to inspect every element. At each step you can look at the middle element and its two neighbors, and the comparison tells you which half of the array must still contain a valley.

1. Handle the trivial case where the array has exactly one element; that single element is the only possible valley, so return index 0.
2. Compare arr[0] and arr[1]. If arr[0] is less than or equal to arr[1], index 0 is a valley because it has no left neighbor to beat it.
3. Compare arr[n - 1] and arr[n - 2] the same way. If the last element is less than or equal to its only neighbor, return index n - 1.
4. If neither boundary qualifies, set low = 1 and high = n - 2 so the search only considers interior elements that have two neighbors on both sides.
5. While low <= high, compute mid and check whether arr[mid] is less than or equal to both arr[mid - 1] and arr[mid + 1]. If so, mid is a valley, so return it.
6. If arr[mid - 1] is smaller than arr[mid], the array is still descending toward the left, so a valley must exist in the left half; set high = mid - 1.
7. Otherwise the array is descending toward the right, so a valley must exist in the right half; set low = mid + 1.
8. The search range shrinks by half on every iteration and a valley is always guaranteed to exist inside [low, high], so the loop always terminates with a valid index.

Java Program

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

import java.util.Arrays;

public class ValleyElementFinder {

    public static int findValley(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0;
        }
        if (arr[0] <= arr[1]) {
            return 0;
        }
        if (arr[n - 1] <= arr[n - 2]) {
            return n - 1;
        }
        int low = 1;
        int high = n - 2;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= arr[mid - 1] && arr[mid] <= arr[mid + 1]) {
                return mid;
            } else if (arr[mid - 1] < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 3, 8, 2, 6, 4, 10};
        int index = findValley(arr);
        System.out.println("Input array: " + Arrays.toString(arr));
        if (index != -1) {
            System.out.println("Valley element found at index " + index + " (value " + arr[index] + ")");
        } else {
            System.out.println("No valley element found");
        }
    }
}

Explanation of the Program

• findValley first handles the single-element array as a special case, since there are no neighbors to compare at all.
• The two boundary checks against arr[0] and arr[n - 1] run before the loop. These let the method return immediately without ever entering the binary search when the valley sits at either end.
• Once both boundary elements are ruled out, low and high are narrowed to the interior indices 1 through n - 2, so every index the loop touches is guaranteed to have two real neighbors.
• Inside the loop, mid is checked against both arr[mid - 1] and arr[mid + 1] together. Only when both comparisons pass does the method return mid.
• When mid is not a valley, the method looks at which neighbor is smaller. A smaller left neighbor means the slope still descends to the left, so the search continues in [low, mid - 1]; otherwise it continues in [mid + 1, high].
• main simply calls findValley on a sample array and prints the resulting index and value, or a “not found” message if the search somehow returns -1 (which never happens given the guarantees above, but keeps the output code defensive).

Step-by-Step Trace

Let’s trace findValley on {9, 7, 5, 3, 8, 2, 6, 4, 10}. Neither boundary qualifies here (9 <= 7 is false and 10 <= 4 is false), so the method enters the loop with low = 1 and high = 7, and the final answer is index 3.

At the start of every iteration, a valley is guaranteed to lie somewhere inside arr[low..high], because the element just outside each end of that range is never smaller than the boundary element next to it.

Examples

Example 1: A Valley in the Interior

For {5, 2, 8}, index 1 is the only interior index, and it is smaller than both of its neighbors.

int[] arr = {5, 2, 8};
int index = findValley(arr);
// index = 1 (valley element 2)

Example 2: A Valley on the Boundary

For {1, 5, 9, 13}, the array is strictly increasing, so the very first element already satisfies the boundary check and the loop never runs.

int[] arr = {1, 5, 9, 13};
int index = findValley(arr);
// index = 0 (valley element 1, boundary case)

Example 3: A Flat Plateau

For {2, 2, 2}, every element is equal, and because the valley check uses <= rather than strict <, index 0 still counts as a valid valley.

int[] arr = {2, 2, 2};
int index = findValley(arr);
// index = 0 (valley element 2, all elements equal)

Common Mistakes to Avoid

These are the mistakes that show up most often when learners implement valley finding for the first time.

• Skipping the boundary checks – running the binary search loop over the full range 0 to n - 1 causes arr[mid - 1] or arr[mid + 1] to read outside the array when mid is 0 or n - 1, throwing ArrayIndexOutOfBoundsException. Narrow the loop to [1, n - 2] and check the two boundary elements separately first.
• Checking only one neighbor – returning mid as soon as arr[mid] <= arr[mid - 1] is true, without also checking arr[mid + 1], reports a false valley whenever the right side is actually smaller. Always require both neighbor comparisons to pass before returning.
• Using strict < instead of <= – comparing with strict less-than silently fails to recognize a valley formed by two equal adjacent elements, such as {4, 2, 2, 6}. Use <= on both sides so flat minima are still detected.
• Assuming the array must be sorted – some learners sort the array first, thinking it makes the search valid; sorting changes the positions of every element and produces the wrong index entirely. The binary search works directly on the array as given.
• Expecting a unique answer – treating the returned index as “the” valley and being confused when a different valid index is expected. The problem allows any valley to be returned, so two correct implementations can report different indices on the same input.

Edge Cases to Test

Before calling the solution complete, walk through these input shapes.

• Single-element array
• Two-element array
• All elements equal (plateau)
• Strictly increasing array
• Strictly decreasing array
• Multiple valleys present
• Valley at index 0 or index n – 1
• Integer.MIN_VALUE or Integer.MAX_VALUE present

Additional Considerations

The binary search solution runs in O(log n) time because the search range is cut in half on every iteration, and it uses only O(1) extra space since it tracks nothing beyond low, high, and mid.

A naive linear scan that checks every index against both neighbors also finds a valid valley, but it runs in O(n) time. That version is still worth knowing because it generalizes trivially to finding every valley in the array, which the binary search version cannot do.

Watch out for Integer.MIN_VALUE and Integer.MAX_VALUE as array values; the comparisons in this algorithm never add or subtract these values, only compare them, so there is no overflow risk even at the extremes.

Interview Follow-up Questions

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

• What if the array is sorted in strictly increasing order? – the first boundary check alone returns index 0 immediately, so the whole method collapses to an O(1) check with no loop needed.
• What if you need every valley, not just one? – switch to a single linear scan comparing each interior element to both neighbors in O(n), since a single binary search can only ever land on one valley by construction.
• What if the input is a 2D grid and you need a 2D local minimum? – extend the idea by comparing the smallest value in the middle row or column to its neighbors, eliminating half the rows or columns each step, similar to 2D peak finding, in roughly O(rows + cols).
• What if the array is enormous and lives in a read-only remote store? – the binary search only ever touches O(log n) elements total, so it can run directly against random-access reads without loading the full array into memory.
• What if duplicates must resolve to the lowest-index valley deterministically? – plain binary search no longer guarantees the lowest index on ties, so you would need to bias the direction of the search toward the left on equal comparisons, or fall back to a linear scan when that guarantee matters more than speed.

Conclusion

Finding a valley element is a great example of how a simple comparison rule, smaller than both neighbors, can be turned into a logarithmic search once you notice that the boundary guarantees always point you toward a half of the array that still contains an answer. The same three-way comparison pattern reappears in peak finding and in several 2D search variants, so it is well worth internalizing.

Try adapting the findValley method to return the lowest valley index, or to count how many valleys exist in total, as good next practice. You can learn more about array-based algorithms like this one in the Arrays category.