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.
1class Solution {
2 public int peakIndexInMountainArray(int[] arr) {
3 int low = 0, high = arr.length - 1;
4 while (low < high) {
5 int mid = low + (high - low) / 2;
6 if (arr[mid] < arr[mid + 1]) {
7 low = mid + 1;
8 } else {
9 high = mid;
10 }
11 }
12 return low;
13 }
14
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[] arr = {0, 2, 1, 0};
18 System.out.println("Peak Index: " + sol.peakIndexInMountainArray(arr));
19 }
20}This Java solution replicates the binary search strategy to find the peak in a mountain array. We initialize low as 0 and high as the last index of the array, iterating until they meet. The peak index is found by leveraging comparisons within the loop.
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.