In this approach, the task is broken into three main steps:
arr[i] > arr[i+1] and arr[i] > arr[i-1].Time Complexity: O(log n) for peak finding and 2 * O(log n) for the two binary searches.
Total: O(log n).
Space Complexity: O(1) because we use a constant amount of space.
1interface MountainArray {
2 int get(int index);
3 int length();
4}
5
6public class Solution {
7 private int findPeakIndex(MountainArray mountainArr) {
8 int left = 0;
9 int right = mountainArr.length() - 1;
10 while (left < right) {
11 int mid = left + (right - left) / 2;
12 if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
13 left = mid + 1;
14 } else {
15 right = mid;
16 }
17 }
18 return left;
19 }
20
21 private int binarySearch(MountainArray mountainArr, int start, int end, int target, boolean isAscending) {
22 while (start <= end) {
23 int mid = start + (end - start) / 2;
24 int value = mountainArr.get(mid);
25 if (value == target) {
26 return mid;
27 }
28 if (isAscending) {
29 if (value < target) {
30 start = mid + 1;
31 } else {
32 end = mid - 1;
33 }
34 } else {
35 if (value > target) {
36 start = mid + 1;
37 } else {
38 end = mid - 1;
39 }
40 }
41 }
42 return -1;
43 }
44
45 public int findInMountainArray(int target, MountainArray mountainArr) {
46 int peak = findPeakIndex(mountainArr);
47 int index = binarySearch(mountainArr, 0, peak, target, true);
48 if (index != -1) {
49 return index;
50 }
51 return binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, false);
52 }
53}The Java solution performs similarly to the C/C++ implementations. It identifies the peak using a binary search, which enables the array to be divided into two segments for additional binary searches to locate the target. Each binary search operation effectively reduces the time complexity to O(log n).
This approach involves directly accessing each element linearly until the condition is satisfied (even though this is not allowed by the problem constraints). It is less optimal and efficient compared to the above implementations, requiring traversal of the entire array.
Time Complexity: O(n) as each element could potentially be checked once.
Space Complexity: O(1) as no extra space is used except for variables.
1class MountainArray:
2 def get(self, index: int) -> int:
3 # Return the element at index in the mountain array.
4 pass
5
6 def length(self) -> int:
7 # Return the length of the mountain array.
8 pass
9
10class Solution:
11 def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
12 length = mountainArr.length()
13 for i in range(length):
14 if mountainArr.get(i) == target:
15 return i
16 return -1The Python brute-force method iterates across each element of the array sequentially, which could come at a significant performance cost. It outputs the index at which the target is present via linear inspection. If not found after iterating through all elements, -1 is returned due to inefficiencies in this simple, non-optimized approach.