Find Student

Easy

0/40

Average time to solve is 10m

Contributed by

15 upvotes

Asked in company

Problem statement

There are 'N' students standing in a line, and their heights are given. But the constraint is that the difference in heights of adjacent students does not exceed 'K', i.e.,

| height[i] - height[i+1] | <= K, where i ∈  (1, N-1)

Your task is to find the position of a student having height 'H'. If no such student is found, return -1.

Note:

Positions are counted starting from 0.
If two or more students have height equal to 'H', return the student with the minimum position.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

 The first line contains 'T', denoting the number of tests.
 For each Test :
     The first line contains three space-separated integers 'N', 'K' and 'H',  denoting the number of students, the maximum difference in adjacent heights, and height of target student, respectively.
     The second line contains an array 'A' of length 'N', denoting the heights of students.

Output Format:

For each test, print an integer, denoting the minimum position of a student having a height equal to 'H'.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= 'T' <= 5
1 <= 'N' <= 10^5
1 <= K, A[i] <= 10^9  i ∈  (1, N)
Note - Sum of 'N' over all test cases does not exceed 10^5.

Time Limit: 1 sec

Sample Input 1:

Sample Output 1

2
1

Explanation for Sample Input 1:

For case 1:
The first student with height equal to 6, is standing at position 2 (starting from 0).

For Case 2:
The first student with height equal to 2, is standing at position 1 (starting from 0).

Sample Input 2:

Sample Input 2:

-1
1

Hint 1

Hint 2

Check the heights of all the students?

Approaches (2)

Approach 1

Approach 2

Brute force

Approach: Run a linear search to find the desired height in an array of heights. If such a student is found, return its position immediately, else return -1.

Algorithm:

Iterate a for loop, i = 0 to N-1.
- If A[i] is equal to 'H', return 'i'.
Return -1.

Time Complexity

O(N), where 'N' is the number of students.
We iterate a simple for loop on the entire array of students. Hence, overall time complexity becomes O(N).

Space Complexity

O(1).

We are using constant space. Hence, overall space complexity becomes O(1).

(100% EXP penalty)

Find Student

Console