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.
1def peakIndexInMountainArray(arr):
2 low, high = 0, len(arr) - 1
3 while low < high:
4 mid = (low + high) // 2
5 if arr[mid] < arr[mid + 1]:
6 low = mid + 1
7 else:
8 high = mid
9 return low
10
11# Example usage
12arr = [0, 2, 1, 0]
13print("Peak Index:", peakIndexInMountainArray(arr))This Python implementation uses a binary search approach. The variables low and high denote the current subarray being examined. During each iteration, the middle index is checked against its next element to decide which half to discard, guiding us to the peak.
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.