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.
1#include <vector>
2#include <iostream>
3
4using namespace std;
5
6int peakIndexInMountainArray(vector<int>& arr) {
7 int low = 0, high = arr.size() - 1;
8 while (low < high) {
9 int mid = low + (high - low) / 2;
10 if (arr[mid] < arr[mid + 1]) {
11 low = mid + 1;
12 } else {
13 high = mid;
14 }
15 }
16 return low;
17}
18
19int main() {
20 vector<int> arr = {0, 2, 1, 0};
21 cout << "Peak Index: " << peakIndexInMountainArray(arr) << endl;
22 return 0;
23}The C++ implementation uses the same logic as C, where a binary search is conducted on the mountain array. The while loop runs until low is equal to high. The decision-making at each step uses comparisons between arr[mid] and arr[mid + 1] to determine which side the peak might be on.
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#
The C solution performs a linear scan from index 1 to arrSize - 2 (exclusive). For each element, it checks if it is larger than its neighbors. If true, the index is returned as the peak index.