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.
1using System;
2
3public class Solution {
4 public int PeakIndexInMountainArray(int[] arr) {
5 int low = 0, high = arr.Length - 1;
6 while (low < high) {
7 int mid = low + (high - low) / 2;
8 if (arr[mid] < arr[mid + 1]) {
9 low = mid + 1;
10 } else {
11 high = mid;
12 }
13 }
14 return low;
15 }
16
17 public static void Main() {
18 Solution sol = new Solution();
19 int[] arr = {0, 2, 1, 0};
20 Console.WriteLine("Peak Index: " + sol.PeakIndexInMountainArray(arr));
21 }
22}The C# solution applies a binary search strategy, where low and high are adjusted based on whether the middle element is less than its succeeding element, indicating the half containing the probable peak. The iteration ceases when low equals high.
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).
1using System;
public class Solution {
public int PeakIndexInMountainArray(int[] arr) {
for (int i = 1; i < arr.Length - 1; ++i) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i;
}
}
return -1; // This should never be reached according to problem constraints.
}
public static void Main() {
Solution sol = new Solution();
int[] arr = {0, 2, 1, 0};
Console.WriteLine("Peak Index: " + sol.PeakIndexInMountainArray(arr));
}
}C# uses a straightforward for loop from the second element to the second last, checking for the peak condition. The index is returned upon meeting the condition, ensuring correctness due to constraints.