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 <stdio.h>
2
3int peakIndexInMountainArray(int* arr, int arrSize){
4 int low = 0, high = arrSize - 1;
5 while (low < high) {
6 int mid = low + (high - low) / 2;
7 if (arr[mid] < arr[mid + 1]) {
8 low = mid + 1;
9 } else {
10 high = mid;
11 }
12 }
13 return low;
14}
15
16int main() {
17 int arr[] = {0, 2, 1, 0};
18 int n = sizeof(arr) / sizeof(arr[0]);
19 printf("Peak Index: %d\n", peakIndexInMountainArray(arr, n));
20 return 0;
21}In this solution, we apply a binary search on the mountain array. The loop continues until low equals high. Each time, we find the mid of the current subarray. If the middle element is less than the next one, it implies the peak is on the right, so we set low to mid + 1. Otherwise, the peak must be at mid or to the left of it, so high is set to mid. The low eventually points to the peak index.
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.