Fastest Horse

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in companies
Goldman SachsChegg Inc.Nagarro Software

Problem statement

There are ‘N’ horses running in ‘N’ different lanes numbered from 1 to ‘N’. You are given an array “FINISHTIME” containing ‘N’ integers where “FINISHTIME[i]” represents the time taken by the ith horse to complete the race.

You are now given ‘Q’ queries, each containing two integers each, ‘L’ and ‘R’. For each query, return the time taken by the fastest horse amongst the horses with numbers {L, L + 1, L + 2, …., R - 1, R} to complete the race.

Note: 
The fastest horse is the one that takes the minimum time to finish the race.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘Q’ that denote the number of horses and number of queries respectively.

The second line of each test case contains ‘N’ space-separated integers, denoting the time taken by each horse to complete the race.

The next ‘Q’ lines contain two space-separated integers ‘L’ and ‘R’ denoting the range of the query.
Output Format : 
For each test case, return the list of integers, where the ith of them denotes the answer of the ith query.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 10000
1 <= Q <= 10000     
1 <= FINISHTIME[i] < 10 ^ 9
0 <= L <= R < N

Time Limit: 1 sec.
Sample Input 1 :
2
5 3
5 3 8 1 9
1 3
5 5
2 4
4 2
2 6 4 8
1 3
3 4
Sample Output 1:
3
9
1
2
4

Explanation for Sample 1:

For the 1st test case:
First Query => The minimum time taken is min(5, 3, 8) = 3.
Second Query => Since there is only one horse in the range [5, 5], we return the time taken by that horse i.e. 9.
Third Query => The minimum time taken is min(3, 8, 1) = 1.

For the second test case:
First Query => The minimum time taken is min(2, 6, 4) = 2.
Second Query => The minimum time taken is min(4, 8) = 4.
Sample Input 2 :
2
10 5
29 11 6 27 4 28 3 24 13 11 
2 4
2 7
4 7
1 3
3 3
6 1
16 12 14 23 20 6 
1 3
Sample Output 2 :
6
3
3
6
6
12
Hint

Can we check the time taken by each horse between ‘L’ and ‘R’ and return the minimum?

Approaches (2)
Brute Force

For each query, we can simply loop between ‘L’ and ‘R’ and store the minimum time taken by a horse to complete the race in a variable, and return the value stored in that variable.

 

Algorithm for Each Query:

 

  • Store the minimum time to complete the race in a variable ‘MINIMUMTIME’ and initialize it with a large enough number, in this case, 10^ 9 is sufficient.
  • Iterate from ‘L’ to ‘R’ and if the time taken by the current horse to complete the race is less than ‘MINIMUMTIME’, update ‘MINIMUMTIME’ to the time taken by the current horse.
  • Return ‘MINIMUMTIME’.
Time Complexity

O(N * Q), where ‘N’ denotes the number of horses and ‘Q’ denotes the number of queries.

 

Note that for each of the ‘Q’ queries, in the worst case we iterate through ‘N’ horses. Therefore the time complexity for each query is O(N), which leads to an overall time complexity of O(N * Q).

Space Complexity

O(N + Q), where ‘N’ denotes the number of horses and ‘Q’ denotes the number of queries.

 

Since we are using an array to store our result -> O(Q).

Since we are storing the time taken by each horse to complete the race -> O(N).

 

Overall Space Complexity -> O(N + Q).

Code Solution
(100% EXP penalty)
Fastest Horse
Full screen
Console