162. Find Peak Element - Solution & Explanation

The problem

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

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,5,6,4]
Output: 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.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] for all valid i.

Approach overview

Problem Overview: You are given an integer array where a peak element is strictly greater than its neighbors. The task is to return the index of any peak element. The array may contain multiple peaks, and you can return any valid one. The challenge is to do better than scanning the entire array.

The problem sits at the intersection of array traversal and binary search. The key observation: if an element is smaller than its right neighbor, a peak must exist on the right side. If it is smaller than the left neighbor, a peak must exist on the left side. This property allows logarithmic search.

Approach 1: Linear Scan (Simpler but Not Optimal) (Time: O(n), Space: O(1))

The most direct solution iterates through the array and checks each element against its neighbors. For index i, verify whether nums[i] > nums[i-1] and nums[i] > nums[i+1]. Edge elements only need one comparison because the array boundaries are treated as negative infinity.

This approach performs a single pass through the array. The first element greater than its next neighbor or the first descending point guarantees a peak. Although the logic is simple and easy to implement, it requires examining up to all n elements, resulting in O(n) time complexity and O(1) space.

Approach 2: Binary Search Approach (Time: O(log n), Space: O(1))

The optimal solution uses binary search by analyzing the slope between adjacent elements. Pick a midpoint mid and compare nums[mid] with nums[mid + 1]. If the right neighbor is larger, the array is ascending at that point, so a peak must exist in the right half. Otherwise, a peak exists in the left half including mid.

This works because any increasing slope eventually leads to a peak, and any decreasing slope already passed one. Each comparison eliminates half of the search space. The algorithm continues shrinking the range until left == right, which points to a peak index.

This approach never needs extra memory and performs at most log2(n) iterations, giving O(log n) time and O(1) space. It demonstrates how binary search can work on unsorted arrays when a structural property (like slope direction) guarantees a solution.

Recommended for interviews: Interviewers typically expect the binary search solution. The linear scan shows you understand the peak definition, but the O(log n) approach proves you can recognize patterns that allow binary search without a fully sorted array. Explaining the slope insight clearly is usually the key step during interviews.

Approach 1: Binary Search Approach

The binary search approach is used to achieve the O(log n) time complexity. Binary search leverages the idea that if an element is not a peak and is less than its right neighbor, then a peak must exist on the right half of the array. Similarly, if it is less than its left neighbor, a peak must exist on the left half of the array. Thus, we keep narrowing down the search window until we find a peak.

Python

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

nums = [1, 2, 3, 1]
index = findPeakElement(nums)
print(f"Peak element index: {index}")

Java

public class Main {
    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        int index = findPeakElement(nums);
        System.out.println("Peak element index: " + index);
    }
}

C++

#include <iostream>
#include <vector>

int findPeakElement(std::vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 1};
    int index = findPeakElement(nums);
    std::cout << "Peak element index: " << index << std::endl;
    return 0;
}

JavaScript

function findPeakElement(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

const nums = [1, 2, 3, 1];
const index = findPeakElement(nums);
console.log(`Peak element index: ${index}`);

#include <stdio.h>

int findPeakElement(int* nums, int numsSize) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int nums[] = {1, 2, 3, 1};
    int index = findPeakElement(nums, 4);
    printf("Peak element index: %d\n", index);
    return 0;
}

using System;

public class PeakElementFinder {
    public static int FindPeakElement(int[] nums) {
        int left = 0, right = nums.Length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void Main() {
        int[] nums = {1, 2, 3, 1};
        int index = FindPeakElement(nums);
        Console.WriteLine($"Peak element index: {index}");
    }
}

This Python solution employs a binary search method. The 'while' loop continues until the search space is reduced to a single element. We adjust either the 'right' or 'left' index by evaluating the mid-element and its right neighbor

Complexity

Time Complexity: O(log n), Space Complexity: O(1)

Try this approach in the editor

Approach 2: Linear Scan (Simpler but Not Optimal)

Though not adhering to the O(log n) requirement, a linear scan is straightforward. It involves checking each element to see if it is a peak element, which can serve as a quick solution, but not fulfilling the constraints in a theoretical context. Practically, it can be used in scenarios where constraints are more relaxed or strictly linear approaches are preferred.

Python

def findPeakElement(nums):
    n = len(nums)
    if n == 1: return 0
    if nums[0] > nums[1]: return 0
    if nums[n - 1] > nums[n - 2]: return n - 1
    for i in range(1, n - 1):
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            return i
    return -1

nums = [1, 2, 3, 1]
index = findPeakElement(nums)
print(f"Peak element index: {index}")

Java

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

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        int index = findPeakElement(nums);
        System.out.println("Peak element index: " + index);
    }
}

C++

#include <iostream>
#include <vector>

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

int main() {
    std::vector<int> nums = {1, 2, 3, 1};
    int index = findPeakElement(nums);
    std::cout << "Peak element index: " << index << std::endl;
    return 0;
}

JavaScript

function findPeakElement(nums) {
    const n = nums.length;
    if (n === 1) return 0;
    if (nums[0] > nums[1]) return 0;
    if (nums[n - 1] > nums[n - 2]) return n - 1;
    for (let i = 1; i < n - 1; i++) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            return i;
        }
    }
    return -1;
}

const nums = [1, 2, 3, 1];
const index = findPeakElement(nums);
console.log(`Peak element index: ${index}`);

#include <stdio.h>

int findPeakElement(int* nums, int numsSize) {
    if (numsSize == 1) return 0;
    if (nums[0] > nums[1]) return 0;
    if (nums[numsSize - 1] > nums[numsSize - 2]) return numsSize - 1;
    for (int i = 1; i < numsSize - 1; ++i) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            return i;
        }
    }
    return -1;
}

int main() {
    int nums[] = {1, 2, 3, 1};
    int index = findPeakElement(nums, 4);
    printf("Peak element index: %d\n", index);
    return 0;
}

using System;

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

    public static void Main() {
        int[] nums = {1, 2, 3, 1};
        int index = FindPeakElement(nums);
        Console.WriteLine($"Peak element index: {index}");
    }
}

This Python solution iterates over the list from the second to the second-last element checking if they qualify as a peak. The linear scan makes this a practical yet less optimal choice for peak finding.

Complexity

Time Complexity: O(n), Space Complexity: O(1)

Try this approach in the editor

Approach 3: Binary Search

We define the left boundary of binary search as left=0 and the right boundary as right=n-1, where n is the length of the array. In each step of binary search, we find the middle element mid of the current interval, and compare the values of mid and its right neighbor mid+1:

If the value of mid is greater than the value of mid+1, there exists a peak element on the left side, and we update the right boundary right to mid.
Otherwise, there exists a peak element on the right side, and we update the left boundary left to mid+1.
Finally, when the left boundary left is equal to the right boundary right, we have found the peak element of the array.

The time complexity is O(log n), where n is the length of the array nums. Each step of binary search can reduce the search interval by half, so the time complexity is O(log n). The space complexity is O(1).

TypeScript

function findPeakElement(nums: number[]): number {
    let [left, right] = [0, nums.length - 1];
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := (left + right) >> 1
		if nums[mid] > nums[mid+1] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Search Approach	Time Complexity: O(log n), Space Complexity: O(1)
Linear Scan (Simpler but Not Optimal)	Time Complexity: O(n), Space Complexity: O(1)
Binary Search	–

Complexity analysis

Approach	Time	Space	When to Use
Linear Scan	O(n)	O(1)	When simplicity matters or when introducing the concept before optimizing
Binary Search	O(log n)	O(1)	Preferred for interviews and large arrays where logarithmic search is expected

Frequently asked questions

Is Find Peak Element easy or hard?

Find Peak Element is generally considered a medium-level problem. The brute force idea is straightforward, but recognizing that binary search works on an unsorted array using slope comparison is the key insight.

How to solve Find Peak Element in O(n)?

Use a linear scan through the array and compare each element with its neighbors. If nums[i] is greater than both adjacent elements, it is a peak. This requires checking each element once, leading to O(n) time and O(1) space.

Find Peak Element Python or Java solution?

Both Python and Java implementations typically use the binary search pattern with two pointers (left and right). Each iteration checks nums[mid] against nums[mid+1] to decide which half to search next, achieving O(log n) time.

What is the best approach for Find Peak Element?

Binary search is the best approach because it reduces the search space by half each step. By comparing nums[mid] with nums[mid+1], you determine which side must contain a peak. This results in O(log n) time complexity and O(1) extra space.

What data structure is used in Find Peak Element?

The problem primarily uses arrays. The optimal algorithm applies binary search logic directly on the array indices without additional data structures, keeping space complexity at O(1).

What is the time complexity of Find Peak Element?

The optimal binary search solution runs in O(log n) time and O(1) space. A simpler linear scan approach runs in O(n) time with constant space. Most interviewers expect the logarithmic solution.

Is Find Peak Element asked at Google, Amazon, or Meta?

Find Peak Element is a common binary search interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests the ability to apply binary search to problems that are not strictly sorted.

Find Peak Element solution and explanation

The problem

Approach overview

Approach 1: Binary Search Approach

Approach 2: Linear Scan (Simpler but Not Optimal)

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Peak Element solution and explanation

The problem

Approach overview

Approach 1: Binary Search Approach

Approach 2: Linear Scan (Simpler but Not Optimal)

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems