Sponsored
Sponsored
This approach leverages the characteristics of a mountain array to achieve an O(log n) time complexity using binary search. The concept is to look for the part of the array where the increase turns into a decrease. We will perform a binary search for the peak index by comparing middle elements and deciding the side that can have the peak element.
Time complexity: O(log n) since we are performing a binary search.
Space complexity: O(1) as we are using a constant amount of extra space.
1function peakIndexInMountainArray(arr) {
2 let low = 0, high = arr.length - 1;
3 while (low < high) {
4 let mid = Math.floor((low + high) / 2);
5 if (arr[mid] < arr[mid + 1]) {
6 low = mid + 1;
7 } else {
8 high = mid;
9 }
10 }
11 return low;
12}
13
14// Example usage
15const arr = [0, 2, 1, 0];
16console.log("Peak Index:", peakIndexInMountainArray(arr));The JavaScript solution deploys binary search by iterating as long as low is different from high. It computes mid and compares arr[mid] with arr[mid + 1], adjusting search bounds based on this comparison.
This approach involves a simple linear scan to find the peak element. Although not achieving the necessary O(log n) time complexity, it serves as a straightforward solution to verify correctness.
Time complexity: O(n) as each element is visited once.
Space complexity: O(1).
1
In this Python solution, a for loop iterates from the first to the second-to-last element. It checks each element for the peak condition. If found, it returns the index, otherwise continues the scan.