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

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 pitfall is assuming that the array is sorted or that there is only one peak, which is not necessarily true.

Approach

To solve this problem efficiently, we can use a binary search approach. A naive solution would involve scanning the entire array to find a peak, which would take O(n) time. However, we can do better by leveraging the properties of the array and using a binary search to achieve O(log n) time complexity.

Naive Solution

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

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. By comparing the middle element with its neighbors, we can decide which half to search next. This reduces the search space by half in each step, leading to a logarithmic time complexity.

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.
- Compare nums[mid] with nums[mid + 1]:
  - If nums[mid] > nums[mid + 1], then the peak is in the left half, so set right = mid.
  - Otherwise, the peak is in the right half, so set left = mid + 1.
When left equals right, the peak element is found at index left.

Code Implementation

public class PeakElementFinder {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // Compare middle element with its right neighbor
            if (nums[mid] > nums[mid + 1]) {
                // Peak is in the left half
                right = mid;
            } else {
                // Peak is in the right half
                left = mid + 1;
            }
        }

        // left and right converge to the peak element
        return left;
    }

    public static void main(String[] args) {
        PeakElementFinder finder = new PeakElementFinder();
        int[] nums1 = {1, 2, 3, 1};
        int[] nums2 = {1, 2, 1, 3, 5, 6, 4};

        System.out.println(finder.findPeakElement(nums1)); // Output: 2
        System.out.println(finder.findPeakElement(nums2)); // Output: 1 or 5
    }
}

Complexity Analysis

The time complexity of the binary search approach is O(log n) because we halve the search space in each step. The space complexity is O(1) as we only use a constant amount of extra space for the pointers and the middle index.

Edge Cases

Potential edge cases include:

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

To handle these cases, the algorithm inherently works without any modifications due to the binary search logic.

Testing

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

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

These test cases cover various scenarios and edge cases to ensure the algorithm works correctly.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and requirements thoroughly.
Think about the properties of the data and how they can be leveraged for optimization.
Break down the problem into smaller parts and solve each part step-by-step.
Practice 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. We covered the problem definition, understanding the problem, different approaches, detailed algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: