162. Find Peak Element

Description

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

Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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: 1 or 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.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

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;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

public class Solution {
    public int findPeakElement(int[] num) {
        int max = num[0];
        int index = 0;
        for(int i=1; i<=num.length-2; i++){
            int prev = num[i-1];
            int curr = num[i];
            int next = num[i+1];
 
            if(curr > prev && curr > next && curr > max){
                index = i;
                max = curr;
            }
        }
 
        if(num[num.length-1] > max){
            return num.length-1;
        }
 
        return index;
    }
}

Solution 3

/**
 * Time complexity : 
 * Space complexity : 
 */

public class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
    
    public int search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}

Solution 4

/**
 * Time complexity : 
 * Space complexity : 
 */

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

Follow up