PPractick

The problem

A hiking app has elevation readings along a trail and wants to mark a summit: any point higher than both its neighbours (the trail's two ends count as having a "neighbour" at minus infinity). There may be many peaks, and any one will do. Scanning the trail is O(n), but binary search works even though the data isn't sorted. If the path is rising at mid (the next reading is higher), there must be a peak somewhere ahead; if it's falling, there must be a peak at mid or behind it.

Example: [1, 2, 3, 1] → 2 (the value 3).

Function signature

int findPeakElement(const vector<int>& nums);  // index of any peak; adjacent values are distinct

Test cases

Input nums	Output	Explanation
[1, 2, 3, 1]	2	3 is higher than 2 and 1
[1, 2, 1, 3, 5, 6, 4]	5	6 is a peak (index 1 would also be accepted)
[1]	0	A single element is a peak
[2, 1]	0	The left end counts, since nums[-1] is minus infinity
[1, 2]	1
[5, 4, 3, 2, 1]	0

(Confirm: nums[i] ≠ nums[i + 1] for all i; positions outside the array count as minus infinity; any peak index is accepted.)

How interviewers phrase it

• "Find a peak element and return its index, in O(log n)" (LeetCode 162).
• The 2D version: find a peak in a grid (S.No 132).
• Related: "find the peak index in a mountain array" (LeetCode 852).

Clarifying questions to ask

1. Is any peak acceptable, or a specific one?
2. Are adjacent elements guaranteed to be different?
3. How are the ends treated? (As bordered by minus infinity.)

Follow-ups to expect

1. "How can binary search work on unsorted data?"
2. "Why does the guarantee about adjacent values matter?"
3. "Why hi = mid in the falling case?"
4. "Complexity?"

Related questions

• First and last occurrence Medium
• Single element in a Sorted Array Medium
• Kth element of 2 sorted arrays Medium
• Search X in sorted array Easy
• Lower Bound Easy
• Upper Bound Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in