Find Peak Element

Medium
60.

Find Peak Element

Find Peak Element is a medium coding problem on arrays and binary search, asked in Yahoo interviews.

A peak element is strictly greater than its neighbors. Given an array nums that strictly increases and then strictly decreases (so it has exactly one peak), return the index of the peak in O(log n) time.

(Either part may be empty: a strictly increasing or strictly decreasing array peaks at an end.)

Example 1

Input
nums = [1,2,3,1]
Output
2
Explanation
3 is the peak, at index 2.

Example 2

Input
nums = [1,2,1,0,-1]
Output
1

Constraints

  • 1 <= nums.length <= 30
  • -1000 <= nums[i] <= 1000
  • nums strictly increases then strictly decreases (exactly one peak).
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Peak Element — Solution in Python, Java & C++

Find Peak Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Yahoo.

Find Peak Element is a medium coding problem on arrays and binary search, asked in Yahoo interviews.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Yahoo
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A peak element is strictly greater than its neighbors. Given an array nums that strictly increases and then strictly decreases (so it has exactly one peak), return the index of the peak in O(log n) time.

(Either part may be empty: a strictly increasing or strictly decreasing array peaks at an end.)

Example 1

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is the peak, at index 2.

Example 2

Input: nums = [1,2,1,0,-1]
Output: 1

Constraints

  • 1 <= nums.length <= 30
  • -1000 <= nums[i] <= 1000
  • nums strictly increases then strictly decreases (exactly one peak).

Hints for Find Peak Element

  1. Hint 1

    Compare nums[mid] with nums[mid+1]: rising means the peak is to the right.

  2. Hint 2

    Falling means the peak is at mid or to the left.

How to solve Find Peak Element

You do not need to see the whole array to find the peak — you only need to know which way the slope runs. Comparing nums[mid] with its right neighbour tells you that: still rising means the peak is further right, already falling means the peak is at mid or to its left. Halve the range on that answer alone.

Approach

  1. Keep a range [lo, hi] and loop while lo < hi.
  2. Take mid = lo + (hi - lo) / 2, which is always strictly less than hi, so mid + 1 is safe to read.
  3. If nums[mid] < nums[mid + 1] you are on the rising side — the peak is strictly right, so lo = mid + 1.
  4. Otherwise you are at or past the summit — set hi = mid, keeping mid as a candidate.
  5. When the range collapses, lo is the peak's index.

Why it works

The array rises strictly and then falls strictly, so the comparison with the right neighbour is a clean test of which side of the summit mid sits on. If it is rising, every index at or left of mid is also below the peak, so discarding them is safe; if falling, everything right of mid is below nums[mid], so the peak is at mid or earlier. The invariant "the peak is in [lo, hi]" survives both branches, and the range always shrinks.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Use hi = mid, not mid - 1 — a falling comparison does not rule mid out.
  • The loop must be lo < hi; with lo <= hi and hi = mid it never ends.
  • mid + 1 is only in bounds because the loop guarantees mid < hi; computing mid with the upper half would break that.
  • A strictly increasing or strictly decreasing array is allowed — the peak is then at an end, which this handles without special cases.

Reference solution

Python

from typing import List

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

Java

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

C++

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

JavaScript

var findPeakElement = function(nums) {
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search