Find Peak Element

LeetCode 162 | Difficulty: Medium

Medium

Problem Description

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^31 <= nums[i] <= 2^31 - 1`

- `nums[i] != nums[i + 1]` for all valid `i`.

Topics: Array, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 160 ms)

Metric	Value
Runtime	160 ms
Memory	N/A
Date	2018-04-13

Solution

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

📜 1 more C# submission(s)

Submission (2018-04-13) — 168 ms, N/A

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

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Precisely define what the left and right boundaries represent, and the loop invariant.