Find a Peak

MediumArraysBinary search243 tests

You get an integer array nums. No two neighbours in it are equal: nums[i] != nums[i + 1] for every i.

An index i is a peak if nums[i] is greater than both of its neighbours. A position outside the array counts as minus infinity, so the first and last values only need to beat their one real neighbour.

Return the index of any peak. If there are several peaks, every one of them is a correct answer. In the examples, Expected lists every correct index, but you return just one number.

Your solution should run in O(log n) time.

Note

A peak always exists. Think about why, and you will see the method.

Hint: look at nums[mid] and nums[mid + 1]. If the values go up from mid to mid + 1, there must be a peak somewhere to the right of mid.

Examples

Example 1

Input:: [4,9,2,6,11,8]
Output:: [1,4]

Index 1 (9 is bigger than 4 and 2) and index 4 (11 is bigger than 6 and 8) are both peaks. Returning 1 or 4 is correct.

Example 2

Input:: [3,5,7,10]
Output:: [3]

The values only go up. The last value, 10, beats its left neighbour, and the right side counts as minus infinity. So index 3 is the only peak.

Example 3

Input:: [-6]
Output:: [0]

With one value, both sides are outside the array, so index 0 is a peak.

Constraints

1 <= nums.length <= 40
-1000 <= nums[i] <= 1000
nums[i] != nums[i + 1] for every valid i

Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.