# 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.