162. Find Peak Element - Explanation

Description

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

You are given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

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,4,5,0]

Output: 5

Explanation: 5 is a peak element and your function should return the index number 5.

Constraints:

1 <= nums.length <= 1000.
-(2^31) <= nums[i] <= ((2^31)-1)
nums[i] != nums[i + 1] for all valid i.

Topics

Array Binary Search

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search - The optimal solution uses binary search on an unsorted array by comparing neighbors to determine which half contains a peak
Array Neighbor Comparison - Understanding how to safely compare elements with their neighbors while handling boundary conditions

1. Brute Force

Intuition

A peak element is greater than its neighbors. Since adjacent elements are guaranteed to be different and elements outside the array are treated as negative infinity, we can scan from left to right. The first time we find an element greater than its next neighbor, we have found a peak. If no such element exists before the last index, the last element itself must be a peak (since the array keeps increasing).

Algorithm

Iterate through the array from index 0 to n-2.
If the current element is greater than the next element, return the current index as a peak.
If the loop completes without finding a peak, return n-1 (the last element is the peak).

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i

        return len(nums) - 1

public class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums.length - 1;
    }
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums.size() - 1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findPeakElement(nums) {
        for (let i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums.length - 1;
    }
}

public class Solution {
    public int FindPeakElement(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums.Length - 1;
    }
}

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        for (i in 0 until nums.size - 1) {
            if (nums[i] > nums[i + 1]) {
                return i
            }
        }
        return nums.size - 1
    }
}

class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        for i in 0..<nums.count - 1 {
            if nums[i] > nums[i + 1] {
                return i
            }
        }
        return nums.count - 1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Search

Intuition

Binary search works here because a peak must exist in any subarray. At each midpoint, if the element is smaller than its left neighbor, a peak exists on the left side. If it is smaller than its right neighbor, a peak exists on the right side. Otherwise, the midpoint itself is a peak. This property allows us to eliminate half the search space each iteration.

Algorithm

Initialize two pointers l = 0 and r = n - 1.
While l <= r:
- Compute the midpoint m.
- If m > 0 and nums[m] < nums[m - 1], move the right pointer to m - 1.
- Else if m < n - 1 and nums[m] < nums[m + 1], move the left pointer to m + 1.
- Otherwise, m is a peak; return m.
Return the result.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = l + (r - l) // 2
            if m > 0 and nums[m] < nums[m - 1]:
                r = m - 1
            elif m < len(nums) - 1 and nums[m] < nums[m + 1]:
                l = m + 1
            else:
                return m

public class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int m = l + (r - l) / 2;
            if (m > 0 && nums[m] < nums[m - 1]) {
                r = m - 1;
            } else if (m < nums.length - 1 && nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                return m;
            }
        }

        return -1;
    }
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;

        while (l <= r) {
            int m = l + (r - l) / 2;
            if (m > 0 && nums[m] < nums[m - 1]) {
                r = m - 1;
            } else if (m < nums.size() - 1 && nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                return m;
            }
        }

        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findPeakElement(nums) {
        let l = 0,
            r = nums.length - 1;

        while (l <= r) {
            let m = Math.floor(l + (r - l) / 2);
            if (m > 0 && nums[m] < nums[m - 1]) {
                r = m - 1;
            } else if (m < nums.length - 1 && nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                return m;
            }
        }

        return -1;
    }
}

public class Solution {
    public int FindPeakElement(int[] nums) {
        int l = 0, r = nums.Length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (m > 0 && nums[m] < nums[m - 1]) {
                r = m - 1;
            } else if (m < nums.Length - 1 && nums[m] < nums[m + 1]) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return l;
    }
}

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        var l = 0
        var r = nums.size - 1

        while (l <= r) {
            val m = l + (r - l) / 2
            if (m > 0 && nums[m] < nums[m - 1]) {
                r = m - 1
            } else if (m < nums.size - 1 && nums[m] < nums[m + 1]) {
                l = m + 1
            } else {
                return m
            }
        }

        return -1
    }
}

class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        var l = 0
        var r = nums.count - 1

        while l <= r {
            let m = l + (r - l) / 2
            if m > 0 && nums[m] < nums[m - 1] {
                r = m - 1
            } else if m < nums.count - 1 && nums[m] < nums[m + 1] {
                l = m + 1
            } else {
                return m
            }
        }

        return -1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Recursive Binary Search

Intuition

This is the same binary search logic implemented recursively. At each step, we compare the middle element with its right neighbor. If the middle is greater, a peak lies in the left half (including mid). Otherwise, a peak lies in the right half. The recursion continues until the search range narrows to a single element, which must be a peak.

Algorithm

Define a recursive function binary_search(l, r).
Base case: If l == r, return l as the peak.
Compute the midpoint m.
If nums[m] > nums[m + 1], recurse on the left half: binary_search(l, m).
Otherwise, recurse on the right half: binary_search(m + 1, r).
Start the recursion with binary_search(0, n - 1).

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        def binary_search(l, r):
            if l == r:
                return l
            m = l + (r - l) // 2
            if nums[m] > nums[m + 1]:
                return binary_search(l, m)
            return binary_search(m + 1, r)

        return binary_search(0, len(nums) - 1)

public class Solution {
    public int findPeakElement(int[] nums) {
        return binarySearch(nums, 0, nums.length - 1);
    }

    private int binarySearch(int[] nums, int l, int r) {
        if (l == r) {
            return l;
        }
        int m = l + (r - l) / 2;
        if (nums[m] > nums[m + 1]) {
            return binarySearch(nums, l, m);
        }
        return binarySearch(nums, m + 1, r);
    }
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        return binarySearch(nums, 0, nums.size() - 1);
    }

private:
    int binarySearch(vector<int>& nums, int l, int r) {
        if (l == r) {
            return l;
        }
        int m = l + (r - l) / 2;
        if (nums[m] > nums[m + 1]) {
            return binarySearch(nums, l, m);
        }
        return binarySearch(nums, m + 1, r);
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findPeakElement(nums) {
        const binarySearch = (l, r) => {
            if (l === r) {
                return l;
            }
            let m = Math.floor((l + r) / 2);
            if (nums[m] > nums[m + 1]) {
                return binarySearch(l, m);
            } else {
                return binarySearch(m + 1, r);
            }
        };

        return binarySearch(0, nums.length - 1);
    }
}

public class Solution {
    public int FindPeakElement(int[] nums) {
        return BinarySearch(nums, 0, nums.Length - 1);
    }

    private int BinarySearch(int[] nums, int l, int r) {
        if (l == r) {
            return l;
        }
        int m = l + (r - l) / 2;
        if (nums[m] > nums[m + 1]) {
            return BinarySearch(nums, l, m);
        }
        return BinarySearch(nums, m + 1, r);
    }
}

func findPeakElement(nums []int) int {
    var binarySearch func(l, r int) int
    binarySearch = func(l, r int) int {
        if l == r {
            return l
        }
        m := l + (r-l)/2
        if nums[m] > nums[m+1] {
            return binarySearch(l, m)
        }
        return binarySearch(m+1, r)
    }

    return binarySearch(0, len(nums)-1)
}

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        fun binarySearch(l: Int, r: Int): Int {
            if (l == r) {
                return l
            }
            val m = l + (r - l) / 2
            return if (nums[m] > nums[m + 1]) {
                binarySearch(l, m)
            } else {
                binarySearch(m + 1, r)
            }
        }

        return binarySearch(0, nums.size - 1)
    }
}

class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        func binarySearch(_ l: Int, _ r: Int) -> Int {
            if l == r {
                return l
            }
            let m = l + (r - l) / 2
            if nums[m] > nums[m + 1] {
                return binarySearch(l, m)
            }
            return binarySearch(m + 1, r)
        }

        return binarySearch(0, nums.count - 1)
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

4. Binary Search (Optimal)

Intuition

We can simplify the binary search by using l < r as the loop condition instead of l <= r. This eliminates extra boundary checks. By always comparing mid with mid + 1, we ensure we move toward a peak. When l == r, we have found the peak without needing additional checks.

Algorithm

Initialize l = 0 and r = n - 1.
While l < r:
- Compute m = (l + r) / 2.
- If nums[m] > nums[m + 1], the peak is at m or to the left, so set r = m.
- Otherwise, the peak is to the right, so set l = m + 1.
When the loop exits, l points to a peak. Return l.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = (l + r) >> 1
            if nums[m] > nums[m + 1]:
                r = m
            else:
                l = m + 1

        return l

public class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;

        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    findPeakElement(nums) {
        let l = 0,
            r = nums.length - 1;

        while (l < r) {
            let m = (l + r) >> 1;
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
}

public class Solution {
    public int FindPeakElement(int[] nums) {
        int l = 0, r = nums.Length - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

func findPeakElement(nums []int) int {
    l, r := 0, len(nums)-1

    for l < r {
        m := (l + r) >> 1
        if nums[m] > nums[m+1] {
            r = m
        } else {
            l = m + 1
        }
    }

    return l
}

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        var l = 0
        var r = nums.size - 1

        while (l < r) {
            val m = (l + r) shr 1
            if (nums[m] > nums[m + 1]) {
                r = m
            } else {
                l = m + 1
            }
        }

        return l
    }
}

class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        var l = 0
        var r = nums.count - 1

        while l < r {
            let m = (l + r) >> 1
            if nums[m] > nums[m + 1] {
                r = m
            } else {
                l = m + 1
            }
        }

        return l
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Incorrect Boundary Handling

When accessing nums[m-1] or nums[m+1], you must check that m > 0 or m < n-1 respectively to avoid array index out of bounds errors. Elements outside the array are conceptually negative infinity, so boundary elements can be peaks if they are greater than their single neighbor.

Using Wrong Loop Condition

Using l <= r versus l < r changes the termination logic significantly. With l < r, when the loop exits, l and r converge to the peak index. With l <= r, you need explicit return statements inside the loop. Mixing these approaches incorrectly leads to infinite loops or missed peaks.

Misunderstanding the Peak Guarantee

The problem guarantees that a peak always exists because adjacent elements are distinct and boundaries are treated as negative infinity. Some solutions incorrectly return -1 or handle the "no peak found" case, which is unnecessary. Understanding why a peak must exist (the array cannot be strictly increasing forever due to the right boundary) helps avoid overcomplicating the solution.