WRONG TURN

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
AppleAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5
1 2 3 2 1
3
4
1 2 3 2
5

Sample Output 1:

2
-1

Explanation of Sample Input 1:

Test Case 1:

According to this test case ‘5’ is the size of the array. In the next line ‘1’, ‘2’, ‘3’, ‘2’, ‘1’ are the elements of our array. In the next line ‘3’ is the target element which we have to search in our mountain array.
In our array index of ‘3’ is ‘2’ so our answer is ‘2’.

Test Case 2:

According to this test case ‘4’ is the size of the array. In the next line ‘1’, ‘2’, ‘3’, ‘2’ are the elements of our array. In the next line ‘5’ is the target element which we have to search in our mountain array.
In our array element‘5’ is not present so we return ‘-1’.
Sample Input 2:
2
3
1 2 1
2
4
1 2 3 1
1
Sample output 2:
1
0
Hint

Try to iterate whole array and check on each index whether it can be a peak or not.

Approaches (2)
Iterative Approach
  • 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’.
Time Complexity

O(N), where ‘N’ denotes the size of the array.

 

As we are traversing the whole array.

Space Complexity

O(1)

 

As,  we are using constant space.

Code Solution
(100% EXP penalty)
WRONG TURN
Full screen
Console