Coding

Find peak element

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array arr of integers. A peak element is defined as an element greater than both of its neighbors. Formally, if arr[i] is the peak element, arr[i - 1] < arr[i] and arr[i + 1] < arr[i].

Find the index(0-based) of a peak element in the array. If there are multiple peak numbers, return the index of any peak number.

Note:

As there can be many peak values, "**true" **is given as output if the returned index is a peak number, otherwise the returned value of index.

**Input **: arr = [1, 2, 3, 4, 5, 6, 7, 8, 5, 1] Output: 7 Explanation: In this example, there is only 1 peak that is at index 7.

**Input **: arr = [1, 2, 1, 3, 5, 6, 4] Output: 1 Explanation: In this example, there are 2 peak numbers at indices 1 and 5. We can consider any of them.

**Input **: arr = [-2, -1, 3, 4, 5]

1 <= arr.length <= 1000
-231 <= arr[i] <= 231 - 1
arr[i] != arr[i + 1] for all valid i.
For arr[0], its left element can be considered as -∞
For arr[n-1], its right element can be considered as -∞

cpp

class Solution {
public:
    int findPeakElement(vector<int> &arr) {
      
    }
};

java

class Solution {
    public int findPeakElement(int[] arr) {
   
    }
}

python

class Solution:
    def findPeakElement(self, arr):

javascript

class Solution {
    findPeakElement(arr) {
     
    }
}

csharp

public class Solution {
    public int FindPeakElement(List<int> arr) {
        // Implement your solution here
    }
}

func findPeakElement(arr []int) int {
    //your code goes here
}

Stuck? Show a way to structure it+

01Treat out-of-range neighbors as negative infinity.
02Compare mid with mid plus one.
03Move toward an increasing slope.
04Keep a candidate peak in the search range.
05Return the converged index.

Reference answer

A peak exists because values outside the array are treated as negative infinity. Binary-search indices: if nums[mid] < nums[mid+1], an increasing slope leads to some peak on the right, so set lo = mid + 1; otherwise a peak exists at mid or to its left, so set hi = mid. When bounds meet, that index is a peak. The proof is directional: repeatedly moving uphill cannot leave the finite array without encountering a local maximum. This does not require the whole array to be sorted. Use mid < hi so reading mid + 1 is safe. Runtime is O(log N) with O(1) space, compared with the valid but slower linear scan.

Then expect these follow-ups

How would duplicates change the guarantee?
Tests: edge cases
What is the simplest linear solution?
Tests: baseline

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question