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 = 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: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 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;
}

//if not found in asscendding art search in descending
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.