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 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 findPeakIndex(mountainArr) {
13 let left = 0;
14 let right = mountainArr.length() - 1;
15 while (left < right) {
16 const mid = Math.floor(left + (right - left) / 2);
17 if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
18 left = mid + 1;
19 } else {
20 right = mid;
21 }
22 }
23 return left;
24 }
25
26 binarySearch(mountainArr, start, end, target, isAscending) {
27 while (start <= end) {
28 const mid = Math.floor(start + (end - start) / 2);
29 const value = mountainArr.get(mid);
30 if (value === target) {
31 return mid;
32 }
33 if (isAscending) {
34 if (value < target) {
35 start = mid + 1;
36 } else {
37 end = mid - 1;
38 }
39 } else {
40 if (value > target) {
41 start = mid + 1;
42 } else {
43 end = mid - 1;
44 }
45 }
46 }
47 return -1;
48 }
49
50 findInMountainArray(target, mountainArr) {
51 const peak = this.findPeakIndex(mountainArr);
52 let index = this.binarySearch(mountainArr, 0, peak, target, true);
53 if (index !== -1) {
54 return index;
55 }
56 return this.binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, false);
57 }
58}The JavaScript solution employs a binary search strategy first to find the peak of the mountain array, then to conduct two additional binary searches on both sections. This ensures that the target is found efficiently with a minimal index. The approach is efficient due to the logarithmic complexity of the binary search.
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.
1interface MountainArray {
2 int get(int index);
3 int length();
4}
5
6public class Solution {
7 public int findInMountainArray(int target, MountainArray mountainArr) {
8 int len = mountainArr.length();
9 for (int i = 0; i < len; i++) {
10 if (mountainArr.get(i) == target) {
11 return i;
12 }
13 }
14 return -1;
15 }
16}The Java implementation performs a linear search across the mountain array elements, comparing each element against the target. As soon as the target is found, its index is returned, otherwise, the loop runs through all elements. Despite being simple, the efficiency is reduced compared to optimized techniques due to increased function calls and potential worst-case traversal across all elements.