1095. Find in Mountain Array(Solution || Leetcode hard || Java)

--

(This problem is an interactive problem.)

You may recall that an array `arr` is a mountain array if and only if:

• `arr.length >= 3`
• There exists some `i` 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: array = [1,2,3,4,5,3,1], target = 3Output: 2Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.`

Example 2:

`Input: array = [0,1,2,4,2,1], target = 3Output: -1Explanation: 3 does not exist in the array, so we return -1.`

Constraints:

• `3 <= mountain_arr.length() <= 104`
• `0 <= target <= 109`
• `0 <= mountain_arr.get(index) <= 109`

SOLUTION:

/**
* // This is MountainArray’s API interface.
* // You should not implement it, or speculate about its implementation
* interface MountainArray {
* public int get(int index) {}
* public int length() {}
* }
*/

class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
//range for binary search
int start = 0;
int end = mountainArr.length() — 1;

int pivot = -1;

//binary search for pivot
while(start <= end){
int mid = start + (end — start)/2;

//to reduce calls we store value of middle element in a variable
int a = mountainArr.get(mid);
int b = mountainArr.get(mid + 1);

//if middle is greater than both elements along its sides then that is our pivot
if(a > b && a > mountainArr.get(mid-1)){
pivot = mid;
break;
}
else if(a < b){
start = mid+1;
}
else{
end = mid;
}
}

//searching target in asscending part of array
int ans = asscendingBinarySearch(target, mountainArr, 0, pivot);
if(ans != -1){
return ans;
}

return descendingBinarySearch(target,mountainArr,pivot+1,mountainArr.length() — 1);
}

//binary search in asscending part
public int asscendingBinarySearch(int target, MountainArray mountainArr,int start, int end){
while(start <= end){
int mid = start + (end — start)/2;
int a = mountainArr.get(mid);

if(a == target){
return mid;
}
else if(a < target){
start = mid + 1;
}
else{
end = mid — 1;
}
}
return -1;
}

//binary search in descending part
public int descendingBinarySearch(int target, MountainArray mountainArr,int start, int end){
while(start <= end){
int mid = start + (end — start)/2;
int a = mountainArr.get(mid);

if(a == target){
return mid;
}
else if(a < target){
end = mid — 1;
}
else{
start = mid + 1;
}
}
return -1;
}
}

Thank you for reading. If you have any queries then, please let me know in the comment section. I will surely bew responsive toward it.