Problem overview
The method findPeakElement receives an Array[Int] named nums in which no two neighbouring elements are equal. It returns the index of any peak, an element that is greater than both of its neighbours. The positions just outside the array count as negative infinity, so the first element only has to beat its right neighbour, and the last only its left one.
For [1, 2, 3, 1] the only peak is 3, so the answer is 2. For [1, 2, 1, 3, 5, 6, 4] there are two peaks, 2 at index 1 and 6 at index 5, and either index is accepted.
A scan that checks every element finds a peak in O(n). The statement asks for O(log n) time and O(1) extra space, which suggests binary search, even though the array is not sorted.
Approach: follow the slope uphill
Binary search needs a test that rules out half of the candidates. Here the test is the slope. Look at an index middle and its neighbours:
- If the left neighbour is larger, walk left: keep stepping left while the next value on the left is larger. The values rise at every step, so the walk has to stop. It stops either at index 0, which beats the negative infinity outside the array, or at an element whose left neighbour is smaller. In the second case the element we stepped from is also smaller, so it is a peak. Either way a peak exists on the left.
- If the right neighbour is larger, the same argument guarantees a peak on the right.
- If neither neighbour is larger,
middleis itself a peak.
So one look at middle either finds the answer or lets you discard half of the window. Because neighbours are never equal, "at least as large" and "strictly larger" give the same result for a real neighbour, and the code can use >=.
When the left neighbour is larger, middle can't be a peak, so the new window can drop it as well: right = middle - 1. The same goes for the right side with left = middle + 1.
Step by step
- Declare
leftandrightasvars covering every index,0andnums.length - 1. A peak can be anywhere. - Loop while
left <= right, so a window of one index is still examined. - Compute
middleasleft + (right - left) / 2. - If
canGoLeft(nums, middle)is true, setright = middle - 1. - Else if
canGoRight(nums, middle)is true, setleft = middle + 1. - Otherwise neither neighbour is larger, so return
middle. - After the loop, return
0. The compiler needs a result on every path, and in practice the loop always returns first.
The helpers are small comparisons with a guard for the array's ends. canGoLeft returns false at index 0, where there is no left neighbour, and otherwise compares nums(i - 1) >= nums(i). canGoRight returns false at the last index and otherwise compares nums(i + 1) >= nums(i).
The solution in Scala
class Solution {
def canGoRight(nums: Array[Int], i: Int): Boolean = {
if (i == nums.length - 1) {
return false
}
return nums(i + 1) >= nums(i)
}
def canGoLeft(nums: Array[Int], i: Int): Boolean = {
if (i == 0) {
return false
}
return nums(i - 1) >= nums(i)
}
def findPeakElement(nums: Array[Int]): Int = {
var left = 0; var right = nums.length - 1
while (left <= right) {
val 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
}
}
Scala details
A semicolon separates two statements on one line, as in var left = 0; var right = nums.length - 1. Normally a line break is enough.
The helpers return a Boolean directly from a comparison, with no if/else needed. The early return false guards the array's ends, so nums(i - 1) and nums(i + 1) are never evaluated with an index outside the array. Reading nums(-1) or nums(nums.length) throws an ArrayIndexOutOfBoundsException.
The if / else if / else chain inside the loop is used as a statement. Two of the branches assign to vars and the last one returns from the method. Arrays are indexed with parentheses in Scala.
Walking through an example
Take [1, 2, 1, 3, 5, 6, 4]. The window is [0, 6] and middle = 3, which holds 3. The left neighbour is 1, not larger. The right neighbour is 5, larger, so left = 4. The window is [4, 6] and middle = 5, which holds 6. Its neighbours are 5 and 4, so neither is larger, and the method returns 5.
Complexity
Every iteration that does not return halves the window, so there are at most about log n iterations, each doing constant work: O(log n) time. The method keeps three Ints, so the extra space is O(1).
Edge cases and common mistakes
- One element.
[5]has no neighbours, both helpers returnfalse, and the answer is 0. - Two elements.
[1, 2]returns 1 and[2, 1]returns 0: the larger element is the peak. - Sorted ascending or descending.
[1, 2, 3, 4, 5]returns 4 and[5, 4, 3, 2, 1]returns 0. The peak is at the last or first index, which only works because the outside counts as negative infinity. - Reading outside the array. Comparing
nums(middle - 1)without the guard fails at index 0, andnums(middle + 1)fails at the last index. The helpers exist to keep these checks in one place. - Several peaks. Any peak is accepted. Which one you get depends on the midpoints, so do not compare your result against one fixed index.
- Equal neighbours. The method assumes
nums(i) != nums(i + 1). With equal neighbours, such as a plateau, a peak isn't guaranteed on either side. - Empty array. The loop never runs and the method returns 0, which is not a valid index. The lesson does not define a result for this case.
Testing
[1, 2, 3, 1]returns 2.[1, 2, 1, 3, 5, 6, 4]returns 5, which is one of the two accepted answers.[5]returns 0.[1, 2, 3, 4, 5]returns 4.
