Problem overview
The function findPeakElement receives an IntArray called nums in which no two neighbouring elements are equal. A peak is an element greater than both of its neighbours, and the positions just outside the array count as negative infinity. So the first element only has to beat its right neighbour, and the last one only its left neighbour. The function returns the index of any peak.
For [1, 2, 3, 1] the answer is 2, because 3 beats 2 and 1. 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.
The array is not sorted, yet the statement asks for O(log n) time and O(1) extra space. A scan from left to right is O(n), so something has to let the search throw half of the array away each time.
Approach: always walk uphill
Look at one index, middle, and compare it with its neighbours. There are three possibilities:
- The left neighbour is at least as large (here, strictly larger). Then the values go up toward the left. Keep walking left while the values keep rising: the walk either stops at an element bigger than both neighbours, or reaches the start of the array, where the element beats the outside value of negative infinity. Either way a peak exists on the left side.
- Otherwise, if the right neighbour is at least as large, the same argument shows that a peak exists on the right side.
- If neither neighbour is larger,
middleis a peak itself.
A larger neighbour is a guarantee of a peak on that side, so the search can drop middle and everything on the other side. That at least halves the window on every step, which gives O(log n).
On [1, 2, 1, 3, 5, 6, 4], the window starts as indices 0 to 6 and the first middle is index 3, value 3. The left neighbour, 1, is smaller; the right neighbour, 5, is larger, so the search moves right and the window becomes indices 4 to 6. The next middle is index 5, value 6. Both neighbours, 5 and 4, are smaller, so the function returns 5.
Step by step
- Set the window.
leftandrightarevars on one line separated by;. A peak can sit at any index, so they start at 0 andnums.size - 1. - Loop while the window is not empty:
left <= right. A window of one index may be the peak, so the condition uses<=. - Compute the middle as
left + (right - left) / 2. It equals(left + right) / 2but cannot overflow, because it never adds the two indices. - Ask whether to go left with the helper
canGoLeft(nums, middle), which already returns aBoolean. - If so, set
right = middle - 1. The left neighbour is larger, somiddleis not a peak and can be dropped. - Otherwise ask
canGoRight(nums, middle)in anelse if. - If so, set
left = middle + 1. - If neither side is larger, return
middlein the finalelse. No neighbour is larger, which is the definition of a peak. - Return 0 after the loop. Kotlin demands a result on every path. The loop always finds a peak first when the array is not empty.
- Write
canGoLeft. At index 0 there is no left neighbour, so it returnsfalse. Otherwise it returnsnums[i - 1] >= nums[i]. - Write
canGoRight. At the last index it returnsfalse. Otherwise it returnsnums[i + 1] >= nums[i].
The solution in Kotlin
class Solution {
fun canGoRight(nums: IntArray, i: Int): Boolean {
if (i == nums.size - 1) {
return false
}
return nums[i + 1] >= nums[i]
}
fun canGoLeft(nums: IntArray, i: Int): Boolean {
if (i == 0) {
return false
}
return nums[i - 1] >= nums[i]
}
fun findPeakElement(nums: IntArray): Int {
var left = 0; var right = nums.size - 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
}
}
The Kotlin details worth a closer look:
- Returning a comparison.
nums[i + 1] >= nums[i]is already aBoolean, so there is no need for anifthat returnstrueorfalse. - Boundary checks come first. The check
i == 0runs beforenums[i - 1]is read. In Kotlin, an index outside an array throwsArrayIndexOutOfBoundsExceptionat run time instead of reading garbage. - Semicolons. Kotlin does not need them at the end of a line. The semicolon in
var left = 0; var right = nums.size - 1is only a separator that puts two statements on one line. if/else ifchain. The branches are tried in order, socanGoRightonly runs whencanGoLeftreturnedfalse.- Why
>=and not>. The statement guarantees neighbours are different, so for this input the two comparisons give the same answer. Either works here.
Complexity
Time: O(log n). Each iteration does a constant amount of work and removes at least half of the window, so there are at most about log2(n) + 1 iterations.
Space: O(1). The search keeps a few Int variables, and the helpers allocate nothing.
Edge cases and common mistakes
- One element. For
[7]both helpers returnfalseat the boundaries, so the function returns 0. - Two elements. For
[1, 2]the first middle is 0, where the right neighbour is larger, so the search moves right and returns 1. For[2, 1]it returns 0. - Strictly increasing or decreasing arrays. The only peak is the last element for
[1, 2, 3, 4, 5](the function returns 4) and the first for a decreasing one. The outside positions at negative infinity are what make these valid. - Several peaks. The function returns one of them. Which one depends on the middles it probes, so the example
[1, 2, 1, 3, 5, 6, 4]gives 5 here, though 1 is also accepted. - Dropping the wrong side. Going left discards the middle and everything to its right, and going right discards the middle and everything to its left. Mixing these up throws away the side that holds the guaranteed peak.
- Reading past the ends. Without the boundary checks in the helpers,
nums[middle - 1]at index 0 throws. - Empty array. With no elements the loop never runs and the function returns 0, which is not a valid index. The problem implies at least one element.
Testing
nums = [1, 2, 3, 1]gives 2.nums = [1, 2, 1, 3, 5, 6, 4]gives 5 (1 is also a correct answer).nums = [7]gives 0.nums = [1, 2]gives 1.nums = [1, 2, 3, 4, 5]gives 4.