Table of Contents
Problem Description:
Given an array of integers arr that represents a mountain, you need to find the peak index. A peak index is an index such that arr[i - 1] < arr[i] > arr[i + 1]. It means the element at the peak index is greater than its adjacent elements.
You can assume that the array arr will be a mountain array, which means it will have a peak.
Sample Input and Expected Output:
Input:
arr = [0, 1, 0]
Output:
Peak index in the mountain array: 1
Input:
arr = [1, 3, 5, 4, 2]
Output:
Peak index in the mountain array: 2
Input:
arr = [0, 10, 5, 2]
Output:
Peak index in the mountain array: 1
Solution in C++:
We can solve this problem using a binary search approach. Since we know that the mountain array has a peak, we can use binary search to find the index where the elements start decreasing again.
#include <iostream>
#include <vector>
int findPeakIndex(std::vector<int>& arr) {
int left = 0;
int right = arr.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
// If the element at mid is less than the next element,
// we are on the ascending part of the mountain, so move left.
left = mid + 1;
} else {
// If the element at mid is greater than or equal to the next element,
// we are on the descending part of the mountain, so move right.
right = mid;
}
}
return left; // The left pointer will point to the peak index.
}
int main() {
std::vector<int> arr1 = {0, 1, 0};
std::vector<int> arr2 = {1, 3, 5, 4, 2};
std::vector<int> arr3 = {0, 10, 5, 2};
int peakIndex1 = findPeakIndex(arr1);
int peakIndex2 = findPeakIndex(arr2);
int peakIndex3 = findPeakIndex(arr3);
std::cout << "Peak index in the mountain array 1: " << peakIndex1 << std::endl;
std::cout << "Peak index in the mountain array 2: " << peakIndex2 << std::endl;
std::cout << "Peak index in the mountain array 3: " << peakIndex3 << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(log n), where n is the size of the arr array. This is because we are performing a binary search, and at each step, we reduce the search space by half.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.