WRONG TURN

Posted: 14 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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   
Approach 1
  • 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’.
Try Problem