Find Peak Element in O(log n) Time Complexity using JavaScript

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] = -∞.

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.

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to find an element in the array that is greater than its neighbors. This is significant in various applications such as finding local maxima in signal processing or identifying peaks in data analysis. A common misconception is to think that the peak must be the global maximum, but any local peak is sufficient.

Approach

To solve this problem, we can use a binary search approach to achieve the required O(log n) time complexity. The naive solution would involve a linear scan of the array, which would take O(n) time. However, this is not optimal for large arrays.

Naive Solution

The naive approach involves iterating through the array and checking each element to see if it is greater than its neighbors. This approach is straightforward but not efficient.

Optimized Solution

The optimized solution uses a binary search approach. The idea is to divide the array into two halves and determine which half contains a peak element. This is based on the observation that if the middle element is not a peak, then at least one of its neighbors must be greater, indicating that a peak must exist in that half of the array.

Algorithm

Here is a step-by-step breakdown of the binary search algorithm:

Initialize two pointers, left and right, to the start and end of the array, respectively.
While left is less than right:
- Calculate the middle index mid.
- If the element at mid is greater than the element at mid + 1, then a peak must be in the left half, so set right to mid.
- Otherwise, a peak must be in the right half, so set left to mid + 1.
When left equals right, the peak element is found, and its index is returned.

Code Implementation

/**
 * @param {number[]} nums
 * @return {number}
 */
function findPeakElement(nums) {
    // Initialize left and right pointers
    let left = 0;
    let right = nums.length - 1;

    // Binary search loop
    while (left < right) {
        // Calculate mid index
        let mid = Math.floor((left + right) / 2);

        // Check if mid element is greater than the next element
        if (nums[mid] > nums[mid + 1]) {
            // Peak is in the left half
            right = mid;
        } else {
            // Peak is in the right half
            left = mid + 1;
        }
    }

    // Return the index of the peak element
    return left;
}

Complexity Analysis

The time complexity of the binary search approach is O(log n) because we are halving the search space in each iteration. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Some potential edge cases include:

Array with a single element: The single element is the peak.
Array with all elements in increasing or decreasing order: The peak will be at the end or the start of the array, respectively.

These cases are handled effectively by the binary search algorithm.

Testing

To test the solution comprehensively, consider the following test cases:

Single element array: [1]
Array with multiple peaks: [1, 2, 1, 3, 5, 6, 4]
Array with increasing elements: [1, 2, 3, 4, 5]
Array with decreasing elements: [5, 4, 3, 2, 1]

Using a testing framework like Jest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and requirements thoroughly.
Think about different approaches and their time complexities.
Break down the problem into smaller, manageable parts.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find a peak element in an array using a binary search approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: