Find Any Local Maximum in an Array

Medium15–20 min

Topics

ArrayBinary Search

Companies

AmazonMicrosoftGoogle

A peak element is one that's strictly greater than both of its neighbors (array edges count as negative infinity on the missing side). Given an array nums where adjacent elements are never equal, return the index of any peak. Aim for O(log n) time. Comparing nums[mid] with nums[mid + 1] tells you which direction climbs toward higher ground — follow it, and you're guaranteed to reach a peak.

Test Case 1:

Input:nums = [1, 2, 3, 1]

Output:2

Explanation:3 is greater than both of its neighbors.

Test Case 2:

Input:nums = [1, 2, 1, 3, 5, 6, 4]

Output:1 or 5

Explanation:Both index 1 (value 2) and index 5 (value 6) are valid peaks — either is accepted.

Test Case 3:

Input:nums = [1]

Output:0

Explanation:A single element has no neighbors, so it's trivially a peak.

Constraints

◆1 ≤ nums.length ≤ 1000
◆-2³¹ ≤ nums[i] ≤ 2³¹ - 1
◆nums[i] ≠ nums[i + 1] for every valid i
◆If multiple peaks exist, returning the index of any one of them is accepted

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 1-12 integers, no two adjacent values equal

1	class Solution {
2	public int findPeakElement(int[] nums) {
3	int lo = 0, hi = nums.length - 1;
4	while (lo < hi) {
5	int mid = lo + (hi - lo) / 2;
6	if (nums[mid] < nums[mid + 1]) {
7	lo = mid + 1;
8	} else {
9	hi = mid;
10	}
11	}
12	return lo;
13	}
14	}
15

↑lo

↑hi

Variables

lo0

hi6

INITIALIZE

Search [0, 6] for any index where the value is greater than both neighbors — climb toward higher ground.

Step 1 / 5

Approach & Solutions

Brute Force — Linear Scan

Brute

Check every index and confirm both of its neighbors (treating the array's edges as negative infinity) are smaller. The first index that qualifies is a peak. It's correct, but it never uses the fact that you can tell which direction climbs toward a peak just by comparing two adjacent values.

TimeO(n)

SpaceO(1)

Java

Try it out

class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean leftOk = (i == 0) || nums[i - 1] < nums[i];
            boolean rightOk = (i == nums.length - 1) || nums[i] > nums[i + 1];
            if (leftOk && rightOk) return i;
        }
        return -1;
    }
}

Optimal — Binary Search

Optimal

Compare nums[mid] with its right neighbor. If nums[mid] < nums[mid + 1], the slope is still climbing, so a peak is guaranteed to exist somewhere to the right (the array can't climb forever) — search right. Otherwise the slope is falling (or mid is itself a local max), so a peak exists at mid or to its left — keep mid in range and search left.

TimeO(log n)