Code Implementation

class Solution:
    def findPeakElement(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left
      

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1])
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};
      

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

var findPeakElement = function(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};
      

Problem Description

Given an array of integers nums, find a peak element and return its index. A peak element is an element that is strictly greater than its neighbors.

• You may assume nums[-1] = -∞ and nums[n] = -∞ where n is the length of the array.
• If the array contains multiple peaks, return the index to any one of the peaks.
• The array may have only one element, in which case that is the peak.
• The solution must not use the same element twice.

Your task is to return the index of any peak element in nums.

Thought Process

The simplest way to solve this problem is to scan through the array and check for each element if it is greater than its neighbors. This is the brute-force approach, but it is not efficient for large arrays.

However, the problem hints at a more efficient solution. Since we only need any peak and not all of them, and since the array can be unsorted, we can use a modified binary search to find a peak in logarithmic time. The key is to compare the middle element with its neighbors and decide which direction to search next.

This is similar to climbing a mountain: if you're standing at a point and the next point is higher, you keep moving in that direction until you reach a peak.

Solution Approach

• Step 1: Initialize two pointers, left and right, at the start and end of the array.
• Step 2: While left < right:
  • Calculate mid = (left + right) // 2 (or language equivalent).
  • Compare nums[mid] and nums[mid + 1]:
  • If nums[mid] < nums[mid + 1], it means there is a peak to the right, so move left to mid + 1.
  • Otherwise, there is a peak at mid or to the left, so move right to mid.
• Step 3: When left == right, this index is a peak, so return left.

This approach works because if you're on a slope (i.e., nums[mid] < nums[mid + 1]), a peak must exist in that direction. If you're on a "downhill" or "plateau", a peak could be at mid or in the other direction.

Example Walkthrough

Consider the input nums = [1, 2, 1, 3, 5, 6, 4].

• First iteration: left = 0, right = 6, mid = 3 (nums[3]=3).
• Compare nums[3]=3 and nums[4]=5. Since 3 < 5, move left to mid + 1 = 4.
• Second iteration: left = 4, right = 6, mid = 5 (nums[5]=6).
• Compare nums[5]=6 and nums[6]=4. Since 6 > 4, move right to mid = 5.
• Third iteration: left = 4, right = 5, mid = 4 (nums[4]=5).
• Compare nums[4]=5 and nums[5]=6. Since 5 < 6, move left to mid + 1 = 5.
• Now left = right = 5. Return 5 as the index of a peak element (nums[5]=6).

The process finds a peak efficiently, without checking every element.

Time and Space Complexity

• Brute-force approach: O(n) time, where n is the length of nums, because we may need to check each element. Space is O(1).
• Optimized (binary search) approach: O(log n) time, because we halve the search space each iteration. Space is O(1) since we only use a few variables.

The binary search is possible because, regardless of the array's order, there is always a peak in any subarray, and the search always moves toward one.

Summary

The "Find Peak Element" problem can be solved efficiently by leveraging a binary search approach. By always moving towards a neighbor that is larger, we guarantee finding a peak in logarithmic time. The key insight is that, due to the definition of a peak and the boundary conditions, a peak always exists, and we do not need to check every element. This makes the solution both elegant and highly efficient.