Sponsored
Sponsored
The binary search approach is used to achieve the O(log n) time complexity. Binary search leverages the idea that if an element is not a peak and is less than its right neighbor, then a peak must exist on the right half of the array. Similarly, if it is less than its left neighbor, a peak must exist on the left half of the array. Thus, we keep narrowing down the search window until we find a peak.
Time Complexity: O(log n), Space Complexity: O(1)
1public class Main {
2 public static int findPeakElement(int[] nums) {
3 int left = 0, right = nums.length - 1;
4 while (left < right) {
5 int mid = left + (right - left) / 2;
6 if (nums[mid] > nums[mid + 1]) {
7 right = mid;
8 } else {
9 left = mid + 1;
10 }
11 }
12 return left;
13 }
14
15 public static void main(String[] args) {
16 int[] nums = {1, 2, 3, 1};
17 int index = findPeakElement(nums);
18 System.out.println("Peak element index: " + index);
19 }
20}This Java code implements the same binary search logic. The main difference is using Java's array operations and syntax. The program finds the peak element's index by narrowing down the search to one half based on the comparison of the mid-element and its right neighbor.
Though not adhering to the O(log n) requirement, a linear scan is straightforward. It involves checking each element to see if it is a peak element, which can serve as a quick solution, but not fulfilling the constraints in a theoretical context. Practically, it can be used in scenarios where constraints are more relaxed or strictly linear approaches are preferred.
Time Complexity: O(n), Space Complexity: O(1)
1
In this approach, we first handle edge cases for the start and end of the array. Then, we iterate through the array to find the first element greater than its neighbors. While the time complexity is O(n), it provides a straightforward implementation.