Problem overview
A peak is an element greater than its neighbours. The method findPeakElement receives an array nums in which no two adjacent elements are equal, and returns the index of any peak. The positions just outside the array, nums[-1] and nums[n], count as negative infinity, so the first element only has to beat its right neighbour and the last element only its left one.
For [1, 2, 3, 1] the answer is 2, because 3 is larger than both neighbours. For [1, 2, 1, 3, 5, 6, 4], either 1 (the value 2) or 5 (the value 6) is accepted. The array is not sorted, yet the statement asks for O(log n) time and O(1) extra space.
Approach: follow the slope uphill
Scanning for a peak is O(n). A binary search is possible because of the infinite borders. Suppose the element at middle is smaller than its right neighbour. Walk right while the values keep rising. The walk has to stop, since the array ends and the border is lower than anything, and the place where it stops is a peak. So a peak exists to the right of middle. The same argument works toward the left. If neither neighbour is larger, middle is itself a peak.
Each look at one element therefore discards one side of the array, which is exactly what binary search needs. The array need not be sorted: it only needs this guarantee of a peak on the rising side.
Take [1, 2, 3, 1]. The window is 0 to 3, so middle is 1, holding 2. Its left neighbour 1 is smaller, so it cannot go left, but its right neighbour 3 is larger, so the window becomes 2 to 3. Now middle is 2, holding 3, and neither neighbour is larger. The method returns 2.
Step by step
- Declare
leftandrightin onevardeclaration, starting at 0 andnums.count - 1. A peak can be at any index. - Loop while
left <= right, so the loop also handles a window of a single index. - Compute
middleasleft + (right - left) / 2, the midpoint written so that the two indices are never added together. - Ask
canGoLeft(nums, middle). If it is true, a peak surely exists on the left, so setright = middle - 1. The left neighbour is larger, somiddleis not a peak. - Otherwise ask
canGoRight(nums, middle), chained withelse if. If true, setleft = middle + 1. - Otherwise return
middle. Neither neighbour is larger, which is the definition of a peak. - Return 0 after the loop. Swift needs a value on every path. For a non-empty array the loop always returns first.
- Write
canGoLeftabovefindPeakElement, with parameters_ nums: [Int], _ i: Intand resultBool. At index 0 there is nothing to the left, so it returnsfalse. Otherwise it returnsnums[i - 1] >= nums[i]. - Write
canGoRightthe same way. At the last index,nums.count - 1, it returnsfalse. Otherwise it returnsnums[i + 1] >= nums[i].
The solution in Swift
class Solution {
func canGoRight(_ nums: [Int], _ i: Int) -> Bool {
if i == nums.count - 1 {
return false
}
return nums[i + 1] >= nums[i]
}
func canGoLeft(_ nums: [Int], _ i: Int) -> Bool {
if i == 0 {
return false
}
return nums[i - 1] >= nums[i]
}
func findPeakElement(_ nums: [Int]) -> Int {
var left = 0, right = nums.count - 1
while left <= right {
let middle = left + (right - left) / 2
if canGoLeft(nums, middle) {
right = middle - 1
} else if canGoRight(nums, middle) {
left = middle + 1
} else {
return middle
}
}
return 0
}
}
The Swift details worth a closer look:
- Booleans returned directly. A comparison like
nums[i - 1] >= nums[i]is already aBool, so it is returned without anif. - Early
return falseprotects the index. Readingnums[-1]ornums[nums.count]would crash the program, because Swift checks array bounds at run time. The boundary checks come first so the neighbour is only read when it exists. - The dead
return 0. Swift's compiler cannot prove that the loop returns, so the final statement is mandatory. It is also the answer for an empty array. - Methods call each other by name. The helpers are methods of the same class, so
findPeakElementcalls them without any prefix, and their order in the class does not matter.
Complexity
Time: O(log n). Every iteration discards at least half of the window, and each iteration does constant work.
Space: O(1). The method uses three integers and calls helpers that use none.
Edge cases and common mistakes
- One element.
[5]returns 0: both helpers returnfalseat their borders, somiddleis returned. - Two elements.
[1, 2]returns 1 and[2, 1]returns 0. - Increasing and decreasing arrays.
[1, 2, 3, 4, 5]returns 4 and[5, 4, 3, 2, 1]returns 0, since the last and the first elements beat their only neighbour. - Several peaks.
[1, 2, 1, 3, 5, 6, 4]returns 5 with this method. The method may return a different peak than the example shows, and any peak is correct. - Equal neighbours. The method relies on adjacent elements being different. With a flat stretch like
[3, 3, 3], the>=comparisons treat equal neighbours as a reason to move, and the method returns 0, which is not a strict peak. - Forgetting the borders. Comparing
nums[middle]withnums[middle - 1]at index 0 crashes the program. - Looking at the wrong side. Moving toward the smaller neighbour can leave the window with no peak at all. Always go toward a larger neighbour.
Testing
nums = [1, 2, 3, 1]gives2.nums = [1, 2, 1, 3, 5, 6, 4]gives5(1 is also valid).nums = [5]gives0.nums = [1, 2, 3, 4, 5]gives4.nums = [5, 4, 3, 2, 1]gives0.
