In this guide, you will get 1095. Find in Mountain Array LeetCode Solution with the best time and space complexity. The solution to Find in Mountain Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
1095. Find in Mountain Array LeetCode Solution in C++
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
*/
class Solution {
public:
int findInMountainArray(int target, MountainArray& mountainArr) {
const int n = mountainArr.length();
const int peakIndex = peakIndexInMountainArray(mountainArr, 0, n - 1);
const int leftIndex = searchLeft(mountainArr, target, 0, peakIndex);
if (mountainArr.get(leftIndex) == target)
return leftIndex;
const int rightIndex =
searchRight(mountainArr, target, peakIndex + 1, n - 1);
if (mountainArr.get(rightIndex) == target)
return rightIndex;
return -1;
}
private:
// 852. Peak Index in a Mountain Array
int peakIndexInMountainArray(MountainArray& A, int l, int r) {
while (l < r) {
const int m = (l + r) / 2;
if (A.get(m) < A.get(m + 1))
l = m + 1;
else
r = m;
}
return l;
}
int searchLeft(MountainArray& A, int target, int l, int r) {
while (l < r) {
const int m = (l + r) / 2;
if (A.get(m) < target)
l = m + 1;
else
r = m;
}
return l;
}
int searchRight(MountainArray& A, int target, int l, int r) {
while (l < r) {
const int m = (l + r) / 2;
if (A.get(m) > target)
l = m + 1;
else
r = m;
}
return l;
}
}; /* code provided by PROGIEZ */
1095. Find in Mountain Array LeetCode Solution in Java
/**
* // 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) {
final int n = mountainArr.length();
final int peakIndex = peakIndexInMountainArray(mountainArr, 0, n - 1);
final int leftIndex = searchLeft(mountainArr, target, 0, peakIndex);
if (mountainArr.get(leftIndex) == target)
return leftIndex;
final int rightIndex = searchRight(mountainArr, target, peakIndex + 1, n - 1);
if (mountainArr.get(rightIndex) == target)
return rightIndex;
return -1;
}
// 852. Peak Index in a Mountain Array
private int peakIndexInMountainArray(MountainArray A, int l, int r) {
while (l < r) {
final int m = (l + r) / 2;
if (A.get(m) < A.get(m + 1))
l = m + 1;
else
r = m;
}
return l;
}
private int searchLeft(MountainArray A, int target, int l, int r) {
while (l < r) {
final int m = (l + r) / 2;
if (A.get(m) < target)
l = m + 1;
else
r = m;
}
return l;
}
private int searchRight(MountainArray A, int target, int l, int r) {
while (l < r) {
final int m = (l + r) / 2;
if (A.get(m) > target)
l = m + 1;
else
r = m;
}
return l;
}
} // code provided by PROGIEZ
1095. Find in Mountain Array LeetCode Solution in Python
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
# Class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(
self,
target: int,
mountain_arr: 'MountainArray',
) -> int:
n = mountain_arr.length()
peakIndex = self.peakIndexInMountainArray(mountain_arr, 0, n - 1)
leftIndex = self.searchLeft(mountain_arr, target, 0, peakIndex)
if mountain_arr.get(leftIndex) == target:
return leftIndex
rightIndex = self.searchRight(mountain_arr, target, peakIndex + 1, n - 1)
if mountain_arr.get(rightIndex) == target:
return rightIndex
return -1
# 852. Peak Index in a Mountain Array
def peakIndexInMountainArray(self, A: 'MountainArray', l: int, r: int) -> int:
while l < r:
m = (l + r) // 2
if A.get(m) < A.get(m + 1):
l = m + 1
else:
r = m
return l
def searchLeft(self, A: 'MountainArray', target: int, l: int, r: int) -> int:
while l < r:
m = (l + r) // 2
if A.get(m) < target:
l = m + 1
else:
r = m
return l
def searchRight(self, A: 'MountainArray', target: int, l: int, r: int) -> int:
while l < r:
m = (l + r) // 2
if A.get(m) > target:
l = m + 1
else:
r = m
return l # code by PROGIEZ
