Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 162] Find Peak Element

Question

link

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

Given an input array where num[i] ? num[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 num[-1] = num[n] = -8.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Show Tags
Array Binary Search

Analysis

This basically is a binary search question. Instead of checking the values, we check the slope (upgoing or downslope).

The important point is the special cases like [1, 2, 3] or [3, 2, 1], we need to return the corner values. Well there’re 2 ways to handle these corner cases.

Solution

First, referring to G4G, the corner case is handled in this way:

if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
        (mid == n-1 || arr[mid+1] <= arr[mid]))
    return mid;

The code 1 below is doing similar things. That code is readable and easy to come up with. I recommend this solution during a interview.

For those who are interested, there is a extremely concise solution thanks to Duplan. I have the Java version posted below as code 2.

Code

Code 1

public class Solution {
    public int findPeakElement(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        } else if (num.length == 1) {
            return 0;
        } else if (num[0] > num[1]) {
            return 0;
        } else if (num[num.length - 2] < num[num.length - 1]) {
            return num.length - 1;
        }
        // now the leftmost edge is increasing
        // and the rightmost edge is also increasing backwards
        return helper(num, 0, num.length - 1);
    }

    public int helper(int[] num, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left + 2 == right) {
            return mid;
        } else if (num[mid] > num[mid + 1]) {
            // middle is decreasing, so peak on the left side
            return helper(num, left, mid + 1);
        } else {
            return helper(num, mid, right);
        }
    }
}

Code 2

public class Solution {
    public int findPeakElement(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        return helper(num, 0, num.length - 1);
    }

    public int helper(int[] num, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left == right) {
            return left;
        } else if (num[mid] > num[mid + 1]) {
            // middle is decreasing, so peak on the left side
            return helper(num, left, mid);
        } else {
            return helper(num, mid + 1, right);
        }
    }
}