Find Peak Element

Problem in Plain English

Given an array with no adjacent equals, return the index of any element strictly greater than its neighbours. Following the uphill slope always leads to a peak, which a binary search exploits in logarithmic time.

Problem Statement

Given a 0-indexed integer array nums, find a peak element, and return its index. A peak element is an element that is strictly greater than its neighbors.

If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] are $-\infty$ , and you must write an algorithm that runs in $O(\log n)$ time.

Constraints

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
nums[i] != nums[i + 1] for all valid i.

Examples

Example 1

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

Index 2 holds 3, strictly above its immediate neighbours 2 and 1. Return index 2 rather than value 3.

Example 2

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

Indices 1 and 5 are both valid peaks: 2 exceeds its neighbours 1 and 1, while 6 exceeds 5 and 4. Either index is accepted; the illustrated output chooses 5.

Example 3

Input: nums = [-2147483648]
Output: 0

The sole element is above both imaginary neighbours, even at the smallest allowed integer value. Return its index 0.

Intuition

A peak is higher than both immediate neighbours; missing neighbours are considered lower than every input value. In [1, 2, 3, 1], index 2 holds 3, above 2 and 1. Following a rising step must eventually reach a fall or the right boundary, so some peak lies in that direction. We only need one peak, allowing binary search to retain a half with a guaranteed peak even if other peaks are discarded.

Approaches

First Drop Scan

Solution Details

Reveal First Drop Scan: intuition, complexity, and code

Intuition

Because the array starts above the imaginary left boundary, the first entry that is taller than its right neighbour must be taller than its left neighbour too. Walking left to right until that first drop therefore lands on a peak by construction.

Step-by-Step Logic

Scan indices i from 0 through n - 2, comparing each value with its right neighbour. On Example 1, [1, 2, 3, 1], start at i = 0.
If nums[i] > nums[i + 1], return i immediately. Otherwise advance; Example 1 advances from 0 to 1 because 1 < 2, then from 1 to 2 because 2 < 3.
Example 1 first falls at i = 2, where 3 > 1, and returns index 2.
If the loop finishes without a fall, return n - 1: every step was rising, so the last element is a peak above the imaginary right neighbour. This also handles a singleton.

Why It Works

Before the first fall, every adjacent comparison is rising because adjacent values are unequal. Thus the first falling index is above its left neighbour (or the imaginary left boundary at index 0) and above its right neighbour by the test: it is a strict peak. If no fall exists, the entire array rises, so the final value exceeds its left neighbour and the imaginary right boundary. The scan therefore always returns a valid peak, although it need not be the largest value.

Dry Run

First Drop Scan: variable states at each step
i before	nums[i]	nums[i + 1]	Comparison	i after / result
0	1	2	1 > 2 is false	advance to 1
1	2	3	2 > 3 is false	advance to 2
2	3	1	3 > 1 is true	return index 2; no increment

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Let n be nums.length. A strictly increasing array requires all n - 1 comparisons before returning the last index, giving O(n) worst-case time. Only the loop index and scalar return are needed: O(1) extra space with no array copies or recursive stack. Example 1 exits early after three comparisons; this baseline does not satisfy the logarithmic requirement.

Code

Solution.java

1class Solution {2    public int findPeakElement(int[] nums) {3        for (int i = 0; i < nums.length - 1; i++) {4            if (nums[i] > nums[i + 1]) {5                return i;6            }7        }8        return nums.length - 1;9    }10}

Hints

Hint 1

Sortedness is not required; a reliable halving decision is enough for binary search.

Hint 2

Compare the middle with its right neighbour to learn whether the slope rises or falls there.

Hint 3

An uphill middle guarantees a peak to the right, and a downhill middle guarantees one at or left of it.

Edge Cases

A single element is a peak by the boundary rule, and the loop returns index 0 without iterating.
A strictly rising array climbs all the way, so the answer is the last index.
A strictly falling array drops immediately, so the answer is index 0.
Nonadjacent repeated values are valid: [1, 3, 1, 3, 1] has peaks at indices 1 and 3; equal adjacent values are excluded.
At integer limits, compare directly rather than subtracting: [-2147483648, 2147483647] returns 1 without arithmetic overflow.

Common Mistakes and Interview Tips

Reading nums[mid + 1] with left <= right can go out of bounds. With left < right, the lower middle always has a right neighbour.
Setting right = mid - 1 can discard a peak at mid; setting left = mid can stall on a two-element rising interval.
Requiring a particular index on multi-peak inputs is incorrect. Return any index strictly above its immediate neighbours.
Treating this as a global-maximum problem misses the local requirement: the first-drop scan may return a smaller peak.
Using a numeric sentinel equal to the smallest integer does not model negative infinity; handle missing neighbours by their positions.
Subtracting neighbours to test a slope may overflow Java int at the allowed limits. Compare the values directly.
Interview tip: explain the boundary conditions that keep at least one peak in the interval. The input need not be sorted, and the discarded half can still have peaks.

Key Takeaway

Binary search needs a halving decision, not a sorted array: a local slope that guarantees a peak in one half is enough.