Show problems as
Classic problem #162MediumArrayBinary Search

Find Peak Element

Real-world version: Survey Line Crest
Tracked in this browser only
Read Find Peak Element on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBitonic Array Search · Binary Search, animated step by step

A survey drone flies one straight line and stores the ground elevation under each of its sample points in elevations, in flight order. Elevations are metres relative to sea level, so they may be negative. No two neighbouring samples came out equal.

Call index i a crest when its elevation beats each neighbour it has: elevations[i] > elevations[i - 1] whenever i > 0, and elevations[i] > elevations[i + 1] whenever i + 1 < elevations.length. Read the ground beyond either end of the line as infinitely deep, which is why a crest always exists.

Return the index of a crest. Several samples may qualify and any one of their indices is accepted. Reading elevations off the drone is slow, so your routine must consult only O(log n) of the samples.

Examples

Example 1

Input
elevations = [-8, -3]
Output
1

The last sample has one neighbour and sits above it, and the ground past the end counts as infinitely deep.

Example 2

Input
elevations = [12, 40, 15, 6]
Output
1

Sample 1 rises above both 12 and 15, and no other index does that, so it is the only crest.

Example 3

Input
elevations = [1, 7, 2, 9, 5]
Output
3

Index 3 beats 2 and 5. Index 1 also beats both of its neighbours, so returning 1 would be accepted as well.

Constraints

  • 1 <= elevations.length <= 1000
  • -2^31 <= elevations[i] <= 2^31 - 1
  • elevations[i] != elevations[i + 1] for every valid i

More than one answer is valid. Return any one of them.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def crest_index(elevations: list[int]) -> int:
Java
public int crestIndex(int[] elevations)

More on the same topics