(This problem is an interactive problem.)
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.
You cannot access the mountain array directly. You may only access the array using a MountainArray interface:
MountainArray.get(k) returns the element of the array at index k (0-indexed).MountainArray.length() returns the length of the array.Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
Example 1:
Input: mountainArr = [1,2,3,4,5,3,1], target = 3 Output: 2 Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:
Input: mountainArr = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.
Constraints:
3 <= mountainArr.length() <= 1040 <= target <= 1090 <= mountainArr.get(index) <= 109In this approach, the task is broken into three main steps:
arr[i] > arr[i+1] and arr[i] > arr[i-1].This C implementation is efficient as it implements a binary search method to find the peak in O(log n) time. After finding the peak, it searches both halves of the mountain array for the target using two separate binary searches. One binary search is for the increasing part (left of the peak) with an increasing order binary search, and another one in the decreasing half (right of the peak) with a decreasing order binary search. As it is a binary search, each takes O(log n) time.
C++
Java
Python
C#
JavaScript
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.
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.
The brute-force approach directly scans through the mountain array from the start to the finish, checking each element against the target. If an element equals the target, it returns the index. Otherwise, it returns -1. This basic method is straightforward but inefficient due to its time complexity.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Binary Search with Peak Finding | Time Complexity: |
| Brute-force Approach | Time Complexity: |
Find Peak Element - Leetcode 162 - Python • NeetCodeIO • 63,861 views views
Watch 9 more video solutions →Practice Find in Mountain Array with our built-in code editor and test cases.
Practice on FleetCode