Problem overview
A peak is an element greater than its neighbours. The method findPeakElement receives a slice nums in which adjacent elements are never equal, and returns the index of any peak. The positions just outside the slice count as minus infinity, so the first element is a peak if it beats its right neighbour, and the last is a peak if it beats its left neighbour.
For [1, 2, 3, 1] the answer is 2, because 3 is larger than 2 and 1. For [1, 2, 1, 3, 5, 6, 4] there are two peaks, the 2 at index 1 and the 6 at index 5, and either index is accepted.
The budget is O(log n) time and O(1) extra space. A scan for a peak is O(n), so the method must halve the search range on each step.
Approach: follow the uphill direction
Binary search normally needs a sorted slice, but here a weaker guarantee is enough. Look at nums[middle] and one neighbour.
- If the left neighbour is larger, the values climb as you go left. Starting from the left neighbour and walking left, you either keep climbing until the slice ends, where the minus-infinity boundary makes the last element you reached a peak, or you stop climbing at a point which is a peak. Either way a peak exists on the left side.
- If the right neighbour is larger, the same argument says a peak exists on the right.
- If neither neighbour is larger,
middleis itself a peak.
So each step throws away the side that cannot be needed, or finds the peak. The range halves, and the loop takes O(log n) steps.
Because neighbours are never equal, "the left neighbour is at least as large" really means "strictly larger". If both neighbours are larger (a valley), either side holds a peak, and the code simply prefers the left. The boundaries are handled by the helper functions.
Trace on [1, 2, 1, 3, 5, 6, 4]. The first middle is 3, with value 3. The left neighbour is 1, not larger. The right neighbour is 5, larger, so left becomes 4. Now left = 4 and right = 6, middle = 5, value 6. Neither neighbour (5 and 4) is larger, so the method returns 5.
Step by step
- Set the window to the whole slice:
left, right := 0, len(nums)-1. A peak can be at any index. - Loop while the window is not empty,
left <= right. Go has nowhile, so this is aforwith only a condition. - Compute
middleasleft + (right-left)/2. - Ask whether to go left. The helper
canGoLeft(nums, i)returns true when the left neighbour is at least as large. The method calls it through the receiver. - If so, drop the right part:
right = middle - 1. The element atmiddlecan't be a peak, since its left neighbour is larger. - Otherwise ask whether to go right with
canGoRight, in anelse if. - If so, set
left = middle + 1. - If neither is true, neither neighbour is larger, so return
middle. - Return 0 after the loop. Go requires a return on every path. The loop finds a peak first for any non-empty slice, so this only matters for an empty one.
- Write
canGoLeft. Ifiis 0 there is nothing on the left, so return false. Otherwise returnnums[i-1] >= nums[i]. - Write
canGoRight. Ifiis the last index, return false. Otherwise returnnums[i+1] >= nums[i].
The solution in Go
type Solution struct{}
func (this Solution) canGoRight(nums []int, i int) bool {
if i == len(nums)-1 {
return false
}
return nums[i+1] >= nums[i]
}
func (this Solution) canGoLeft(nums []int, i int) bool {
if i == 0 {
return false
}
return nums[i-1] >= nums[i]
}
func (this Solution) findPeakElement(nums []int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)/2
if this.canGoLeft(nums, middle) {
right = middle - 1
} else if this.canGoRight(nums, middle) {
left = middle + 1
} else {
return middle
}
}
return 0
}
Go details in this code
- Methods, not classes. Go has no classes.
Solutionis an empty struct, and the functions with a receiver in parentheses before the name are its methods. - The receiver name
thisis an ordinary identifier here, not a keyword. Many Go programs would write a short name such ass, butthiscompiles and works the same. - Boolean returns. A comparison such as
nums[i+1] >= nums[i]is already abool, so it is returned directly instead of through anif. - The boundary checks come first. Reading
nums[-1]ornums[len(nums)]would panic with an index-out-of-range error, so each helper tests the edge before touching the neighbour. This is what implements the minus-infinity rule: an edge element has no larger neighbour on the outside. - Helper order. The methods can be declared in any order in the file.
Complexity
Time: O(log n). Each iteration reduces the window to at most half of its size, and each helper call does constant work.
Space: O(1). Only left, right and middle; the loop is iterative, so there is no call stack growth.
Edge cases and common mistakes
- One element.
[5]hasmiddle = 0. Both helpers return false at the boundary, so the method returns 0. - Two elements.
[1, 2]returns 1 and[2, 1]returns 0. - Peak at an end. For a strictly increasing slice the answer is the last index, and for a decreasing one it is index 0. Dropping the boundary checks would panic.
- Several peaks. The method returns one of them, which one depending on where the middles fall. Any peak is valid.
- Setting
right = middleorleft = middle. The middle element was ruled out, so moving past it with- 1and+ 1avoids loops that never end. - Comparing only with one side. Checking just the right neighbour is not enough to declare a peak; both sides must be considered, which is what the two helpers do together.
- Empty slice. The loop never starts, so the method returns 0 although there is no peak. The problem has no empty input.
Testing
[1, 2, 3, 1]gives 2.[1, 2, 1, 3, 5, 6, 4]gives 5 (1 would also be valid).[5]gives 0.[1, 2]gives 1, and[2, 1]gives 0.