Sponsored
Sponsored
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
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.
1 int Get(int index);
int Length();
}
public class Solution {
public int FindInMountainArray(int target, MountainArray mountainArr) {
int len = mountainArr.Length();
for (int i = 0; i < len; i++) {
if (mountainArr.Get(i) == target) {
return i;
}
}
return -1;
}
}This brute-force C# method executes a basic iteration from the start to the end of the mountain array, checking if each element matches the target. If a match is discovered, it returns the index; otherwise, it continues to scan till the end, eventually returning -1, marking it as inefficient for larger datasets.