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.
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 findPeakIndex(self, mountainArr: 'MountainArray') -> int:
12 left, right = 0, mountainArr.length() - 1
13 while left < right:
14 mid = left + (right - left) // 2
15 if mountainArr.get(mid) < mountainArr.get(mid + 1):
16 left = mid + 1
17 else:
18 right = mid
19 return left
20
21 def binarySearch(self, mountainArr: 'MountainArray', start: int, end: int, target: int, is_ascending: bool) -> int:
22 while start <= end:
23 mid = start + (end - start) // 2
24 value = mountainArr.get(mid)
25 if value == target:
26 return mid
27 if is_ascending:
28 if value < target:
29 start = mid + 1
30 else:
31 end = mid - 1
32 else:
33 if value > target:
34 start = mid + 1
35 else:
36 end = mid - 1
37 return -1
38
39 def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
40 peak = self.findPeakIndex(mountainArr)
41 index = self.binarySearch(mountainArr, 0, peak, target, True)
42 if index != -1:
43 return index
44 return self.binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, False)The Python implementation follows the same logic as the previously described solutions: a binary search to find the peak, followed by two additional binary searches on the segregated parts of the array to locate the target efficiently.
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 get(index) {
3 // Returns the element of the array at index 'index'.
4 }
5
6 length() {
7 // Returns the number of elements in the mountain array.
8 }
9}
10
11class Solution {
12 findInMountainArray(target, mountainArr) {
13 let len = mountainArr.length();
14 for (let i = 0; i < len; i++) {
15 if (mountainArr.get(i) === target) {
16 return i;
17 }
18 }
19 return -1;
20 }
21}Using JavaScript's brute-force search, the solution deploys a for loop to walk through each element of the mountain array. It checks for a match with the target element, returning the index if found, or -1 after scanning the full array, making it less favorable for large inputs due to its lengthy evaluation process.