Last Updated: 14 Mar, 2021
WRONG TURN
Moderate
Asked in companies
Ninja started working as a delivery boy for ‘Coding Ninja’and used to deliver goodies to the students. As usual, he is on his way to deliver the goodies but he takes a wrong turn and arrives at the wrong location. So now he sees the map of that locality and looks for his target on the map. The map contains the house number in the form of a special array i.e in the form of a ‘Mountain Array’.
A Mountain array(‘ARR’) is an array data structure that has the following properties:
1. |ARR| >= 3
2. There exists some ‘i’ with 0 < i < arr.length-1 such that:
1. ARR[0] < ARR[1] < . . . < ARR[i-1] < ARR[i]
2. ARR[i] > ARR[i+1] > . . . > ARR[ARR.length-1]
Note:
You can't access the mountain array directly. You may only access the array using a MountainArray interface:
1. MountainArray.get(k) returns the element of the array at index k (0-indexed).
2. MountainArray.length() returns the length of the array.
Your task is to find the index of the target element. In case there is more than one same element in the array return the smaller index and in case the element is not present in the array return ‘-1’.
Follow-up:
Try to solve it at max 100 ‘MountainArray.get(k)’calls.
Input Format:
The first line of input contains a ‘T’ number of test cases.
The first line of the test case, contains an integer ‘N’ denoting the size of the array.
The second line of each test case contains ‘N’ space-separated integers.
The third line of each test case contains, an integer ‘M’ denoting the target element i.e the element which you have to search in the mountain array.
Output Format:
For each test case, return the minimum index of the target element in case the element is not present return ‘-1’.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
You will be provided with only the object of the mountain array and target element.
Constraints:
1 <= T <= 100
3 <= N <= 10^3
0 <= ARR[i] <= 10^4
0 <= M <= 10^4
Time Limit: 1 sec
Approaches
- The simplest approach is to traverse the array starting from ‘0’upto the MOUNTAIN_ARRAY.length() like
- Iterate a for loop ‘i’ from ‘0’ to the length of 'MOUNTAIN_ARRAY'
- ‘X = MountainArray.get(i)’ it will return ‘i’ element of 'MOUNTAIN_ARRAY'
- Now check if ‘X’ is equal to the target element ‘M’ or not.
- If we found that element we return that equivalent index ‘i’.
- Else if we don’t find that element after traversing the whole array we return ‘-1’.
- First, find the peak index from the mountain array by using a recursive function.
- For this recursive function, we define three variables 'MID', 'LEFT', and 'RIGHT'.
- Where 'MID' refers to the index of the middle element of the array, 'RIGHT' refers to the index of middle element+1, and 'LEFT' refers to the index of middle element-1.
- We use these conditions in our recursive function FIND_PEAK() for finding peak element
if( mid > right and mid > left)
{
return mid
}
else if(mid > right and mid < left)
{
return findPeak(0, mid, MountainArray)
}
else if(mid < right and mid > left)
{
return findPeak(mid, right, MountainArray)
}- On the basis of the obtained peak index, we partition the array into two parts left and right.
- Now we first search its left side using Binary search, as we know in mountain array left subarray is sorted in ascending order
- If we found that element we return the index of that element else we search in our right array.
- Now we search the right side using binary search as we know our right mountain subarray is sorted in descending order.
- If we found that element we return the index of that element else we return ‘-1’.
Similar problems