Find in Mountain Array
Problem Description
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3- There exists some
iwith0 < i < arr.length - 1such 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 indexk(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() <= 104
- 0 <= target <= 109
- 0 <= mountainArr.get(index) <= 109
Solve it on LeetCode
Approaches
1. Brute Force Linear Search
Intuition:
In a mountain array, there exists a peak element after which elements start decreasing. For a brute force approach, one can simply iterate over the entire array to find the target. This involves two phases:
- Traverse from the start to the peak (increasing sequence).
- Traverse from the peak to the end (decreasing sequence).
Steps:
- Iterate through the array from the start to the peak to look for the target.
- If not found, iterate from the peak to the end.
Code:
- Time Complexity: O(n), as we may have to look at each element in the worst case twice.
- Space Complexity: O(1) - No additional space used apart from variables.
2. Optimized Binary Search
Intuition:
Utilizing the properties of the mountain array, we can apply binary search methods to efficiently find the peak and then search for the target in both increasing and decreasing sequences separately.
Steps:
- Use a binary search to find the peak of the mountain array.
- Perform a binary search on the increasing sequence from the start to the peak to find the target.
- If the target is not found, perform a binary search on the decreasing sequence from the peak to the end.
Code:
- Time Complexity: O(log n), The binary search is applied three times (once to find peak and twice to find target).
- Space Complexity: O(1) - No additional space used apart from variables.