LESSON 272 OF 410 · BINARY SEARCH

Find Peak Element in JavaScript: O(log n) Binary Search

Practice O(log n) Read the full explanation

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1, 2, 3, 1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

STEP 1 OF 15

Guided

Ctrl + Enter to check

JAVASCRIPT · BINARY SEARCH

Find Peak in JavaScript, explained

Problem overview

The method findPeakElement(nums) receives an array of numbers in which no two neighbouring values are equal. A peak is an element larger than both of its neighbours. The method returns the index of any one peak. The two ends count too: the problem treats the positions before the first element and after the last as minus infinity, so the first element is a peak if it is larger than the second, and the last is a peak if it is larger than the one before it.

In [1, 2, 3, 1] the value 3 at index 2 is the only peak, so the answer is 2. In [1, 2, 1, 3, 5, 6, 4] there are two peaks, 2 at index 1 and 6 at index 5, and either index is a correct answer. The array may hold many peaks, but it always holds at least one.

The lesson also sets a budget: O(log n) time and O(1) extra space. A single scan from left to right would find a peak in O(n), so the budget is telling you to discard half of the array at every step.

Approach: follow the slope uphill

Pick any index middle and look at its neighbours. There are three cases:

The left neighbour is larger. Walk left from middle: the values go up while you move left, and they can't go up forever, because the array ends and the value beyond the end counts as minus infinity. So a peak exists somewhere on the left side.
The right neighbour is larger. By the same argument, a peak exists on the right side.
Neither neighbour is larger. Then middle is itself a peak.

Because neighbours are never equal, every index falls into one of these cases. When both neighbours are larger, both sides contain a peak and either choice is safe. Each step throws away half of the window, so there are about log2(n) steps. That is binary search, except the thing you search for is not a given value: you search for a place where the slope stops rising.

For [1, 2, 1, 3, 5, 6, 4] the window starts as indices 0 to 6, and the middle is index 3 (value 3). Its left neighbour 1 is smaller and its right neighbour 5 is larger, so the search moves right. The window is now indices 4 to 6 with middle 5 (value 6). Both neighbours are smaller, so index 5 is returned.

Step by step

Track a window with two indices. left starts at 0 and right at nums.length - 1, because a peak can be at any index. A single let declares both.
Loop while the window is not empty. The condition is left <= right. With <= a window holding one index still gets examined, and that one index may be the peak.
Find the middle. (left + right) >> 1 halves the sum and drops the fraction. Plain / 2 would produce an index such as 2.5, because JavaScript numbers are not integers.
Ask whether to go left. A helper, canGoLeft(nums, i), answers whether a left neighbour at least as large exists. Call it as this.canGoLeft, since it is a method of the class.
Shrink from the right. If the left side holds a peak, set right = middle - 1. middle itself can be dropped, because its left neighbour is larger and it can't be a peak.
Otherwise ask whether to go right with canGoRight, and set left = middle + 1 if so.
Otherwise return middle. Neither neighbour is larger, which is the definition of a peak.
Return 0 after the loop. The loop always returns before the window empties, so this line is only a safe default. Without it the method would return undefined if the loop ever ended.
Write the helpers. canGoLeft returns false at index 0, where there is nothing on the left, and otherwise returns whether nums[i - 1] >= nums[i]. canGoRight returns false at the last index and otherwise returns whether nums[i + 1] >= nums[i]. A comparison is already a boolean, so it is returned directly.

The solution in JavaScript

class Solution {

    canGoRight(nums, i) {
        if (i == nums.length - 1) {
            return false
        }
        return nums[i + 1] >= nums[i]
    }

    canGoLeft(nums, i) {
        if (i == 0) {
            return false
        }
        return nums[i - 1] >= nums[i]
    }
    
    findPeakElement(nums) {
        let left = 0, right = nums.length - 1
        while (left <= right) {
            let middle = (left + right) >> 1
            if (this.canGoLeft(nums, middle)) {
                right = middle - 1
            } else if (this.canGoRight(nums, middle)) {
                left = middle + 1
            } else {
                return middle
            }
        }
        return 0
    }
}

A few JavaScript details are worth knowing:

Methods are called through this. Inside a class, writing canGoLeft(nums, middle) alone looks for a variable of that name and fails with a ReferenceError. Methods are reached with this.canGoLeft(...).
>> 1 works on 32-bit integers. The operator converts its operand to a 32-bit integer before shifting, so it also floors the result. That is fine for any array that fits in memory. Math.floor((left + right) / 2) gives the same index and avoids the 32-bit conversion.
The comparison >= never sees equal neighbours in valid input, so it behaves like >. If equal neighbours were allowed, a plateau could hide the peak and this approach would fail.
== against ===. The helpers compare two numbers with ==, which is safe here. In general, prefer ===.

Complexity

The window halves on every pass, so the loop runs at most about log2(n) times. Each pass does a constant amount of work: one midpoint, and at most two comparisons through the helpers. Time is O(log n). The method keeps only left, right and middle, so extra space is O(1).

Edge cases and common mistakes

A single element. [5] returns 0. Both helpers return false there, because each boundary check fires, so the element is a peak by default.
Two elements. [1, 2] returns 1, and [2, 1] returns 0. The ends are peaks if they beat their only neighbour.
Strictly rising or falling arrays. [1, 2, 3, 4, 5] returns 4 and [5, 4, 3, 2, 1] returns 0. The peak sits at an end, which is why the helpers must handle index 0 and the last index instead of reading outside the array. Reading nums[-1] gives undefined, and every comparison with undefined is false, so it would not crash but the logic would rest on a value that does not exist.
Using left < right. The loop would stop before looking at a window of one index and could miss the answer.
Setting right = middle instead of middle - 1. The window may then stop shrinking, and the loop never ends.
Several valid answers. For [1, 2, 1, 3, 5, 6, 4] this method returns 5. Checking for exactly 1 would reject a correct answer, so test by checking the neighbours of the returned index.

Testing

Try these in the editor:

[1, 2, 3, 1] returns 2.
[1, 2, 1, 3, 5, 6, 4] returns 5.
[5] returns 0.
[1, 2, 3, 4, 5] returns 4.
[5, 4, 3, 2, 1] returns 0.

Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free