341. Any Peak Will Do
A hiking guide has the elevation of every marker along a trail. Two neighbouring markers never have the same elevation. A marker is a summit if it is strictly higher than the marker before it and the marker after it; the ends of the trail count as having nothing beyond them, so an end marker only needs to beat its single neighbour.
Given the array heights, return the index of any summit. There may be several, and any one of them is accepted. A single scan would take O(n); your solution should find one in O(log n) time. The array is guaranteed to have at least one summit.
Example 1
- Input:
- heights = [2,5,3]
- Output:
- 1
- Explanation:
Index 1 (height 5) is higher than both neighbours.
Example 2
- Input:
- heights = [1,3,2,6,4]
- Output:
- 3
- Explanation:
Both index 1 and index 3 are summits; either answer is accepted.
Constraints
1 ≤ heights.length ≤ 106
-109 ≤ heights[i] ≤ 109heights[i] ≠ heights[i + 1] for every valid i.
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)