Find Peak Element medium

Problem Statement

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

Given an 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 assume that nums[-1] = nums[n] = -∞.

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: Either 5 or 6 are peak elements. Your function can return either index number 5 or 6

Steps

1. Handle Edge Cases: If the input array is empty or has only one element, return 0 (or the only index).
2. Linear Scan: Iterate through the array, comparing each element with its neighbors.
3. Peak Condition: An element nums[i] is a peak if nums[i] > nums[i-1] and nums[i] > nums[i+1]. Handle edge cases for the first and last elements separately.
4. Return Index: If a peak is found, return its index i.

Explanation

The problem leverages the property that a peak element is strictly greater than its adjacent elements. The solution uses a linear scan to efficiently check this condition for each element. The boundary conditions (first and last element) are handled by assuming that elements outside the array are negative infinity, ensuring that the first and last elements can be considered peaks if they are greater than their single neighbor.

Code (Java)

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;

        //Handle edge cases
        if (n == 0) return 0; 
        if (n == 1) return 0;

        //Linear scan
        for (int i = 0; i < n; i++) {
            boolean isPeak = true;

            //Check neighbors. Handle edge cases for first and last elements.
            if (i > 0 && nums[i] <= nums[i - 1]) isPeak = false;
            if (i < n - 1 && nums[i] <= nums[i + 1]) isPeak = false;

            if (isPeak) return i;
        }

        //Should not reach here if at least one peak exists (as problem states)
        return -1; //Add this for completeness, though the problem guarantees a peak exists.
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. This is because we perform a linear scan of the array.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We only use a few integer variables.