Peak of an Increasing-Then-Decreasing Array
Snap Inc.● MediumFULLTIMEONSITE INTERVIEWProblem statement
You are given an array nums. The numbers strictly increase up to one position, called the peak, and then strictly decrease until the end of the array.
Return the index of the peak. The interview asked for a binary search, so try to solve this in O(log n) time.
Follow-up to think about (not judged): suppose neighbors can be equal, so the numbers never go down before the peak and never go up after it. Can you still use binary search?
Function
findPeak(nums: int[]) → intExamples
Example 1
nums = [1,3,5,4,2]return = 2The numbers go up through 1, 3, 5 and then down through 4, 2. The largest number 5 is at index 2.
Example 2
nums = [0,10,5,2]return = 1There is one step up, from 0 to 10, and then the numbers go down. The peak is at index 1.
Example 3
nums = [-5,-2,-9]return = 1All the numbers can be negative. -2 is larger than both neighbors, so the peak is at index 1.
Constraints
3 <= nums.length <= 5000-10^9 <= nums[i] <= 10^9- There is an index
pwith0 < p < nums.length - 1such thatnums[0] < nums[1] < ... < nums[p]andnums[p] > nums[p + 1] > ... > nums[nums.length - 1].