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

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 be to iterate through the array and check each element, but this would result in O(n) time complexity, which is not optimal.

Naive Solution

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

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.

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 update right to mid.
- Otherwise, a peak must be in the right half, so update left to mid + 1.
When left equals right, the peak element is found, and its index is returned.

Code Implementation

def findPeakElement(nums):
    # Initialize left and right pointers
    left, right = 0, len(nums) - 1
    
    # Perform binary search
    while left < right:
        mid = (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

# Example usage
print(findPeakElement([1, 2, 3, 1]))  # Output: 2
print(findPeakElement([1, 2, 1, 3, 5, 6, 4]))  # Output: 1 or 5

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 only a constant amount of extra space.

Edge Cases

Potential edge cases include:

Array with a single element: The single element is the peak.
Array with two elements: The larger element is the peak.
Array with all elements in increasing or decreasing order: The peak is at the end of the array.

These edge cases are handled effectively by the binary search algorithm.

Testing

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

Single element array: [1]
Two elements array: [1, 2] and [2, 1]
Array with multiple peaks: [1, 3, 2, 4, 3]
Array with all increasing or decreasing elements: [1, 2, 3, 4, 5] and [5, 4, 3, 2, 1]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Think about the properties of the problem that can be exploited, such as the binary search approach in this case.
Break down the problem into smaller parts and solve each part step-by-step.
Practice solving similar problems to improve problem-solving skills and familiarity with different algorithms.

Conclusion

In this blog post, we discussed how to find a peak element in an array using a binary search approach to achieve O(log n) time complexity. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: