Skip to content
AI360Xpert
Back to Binary Search
Medium

Find Peak Element

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.

Examples

Input:nums = [1,2,3,1]
Output:2
3 is a peak element and your function should return the index number 2.
Input:nums = [1,2,1,3,5,6,4]
Output:5
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.

Approach

Iterate through the array and check if the current element is greater than its neighbors. Since `nums[-1]` and `nums[n]` are considered negative infinity, we only need to check if the current element is greater than the next element. The first such element we find is a peak.

Complexity Analysis

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

This approach does not meet the O(log n) time complexity requirement.

Solution.java
class Solution {    public int findPeakElement(int[] nums) {        for (int i = 0; i < nums.length - 1; i++) {            if (nums[i] > nums[i + 1]) {                return i;            }        }        return nums.length - 1;    }}