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.
1public interface 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, bool 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 C# solution also leverages binary search to efficiently find the peak and then searches on both the ascending and descending segments of the mountain array. This strategy ensures that the solution remains optimal with a time complexity of 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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Mockup of MountainArray, simulating interface.
6class MountainArray {
7public:
8 int get(int index) const;
9 int length() const;
10};
11
12int findInMountainArray(int target, const MountainArray &mountainArr) {
13 int len = mountainArr.length();
14 for (int i = 0; i < len; ++i) {
15 if (mountainArr.get(i) == target) {
16 return i;
17 }
18 }
19 return -1;
20}The C++ brute-force solution iterates with a loop, accessing each value one-by-one, and checking for equality with the target value. It returns the index if a match is found and -1 if the entire array is traversed without finding the target. This is straightforward but is less optimized since it calls the get function repeatedly and traverses each element.