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#include <iostream>
using namespace std;
int peakIndexInMountainArray(vector<int>& arr) {
for (int i = 1; i < arr.size() - 1; ++i) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i;
}
}
return -1;
}
int main() {
vector<int> arr = {0, 2, 1, 0};
cout << "Peak Index: " << peakIndexInMountainArray(arr) << endl;
return 0;
}The C++ implementation iterates linearly over the mountain array to find the peak. It checks if the current element is greater than its previous and next neighbors, ensuring it's the peak before returning its index.