Last Updated: 20 Apr, 2021
Fastest Horse
Moderate
Asked in companies
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.
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.
Approaches
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’.
A segment Tree is a data structure that allows us to perform range queries efficiently. In a minimum segment tree, at any node, we store the minimum value of all the leaf nodes present in the subtree rooted at that node. Similarly, for maximum segment trees, we store the maximum, for sum segment trees we store the sum, etc.
To learn more about segment trees, wiki is a good source to get started.
The first step in this approach is to build the minimum segment tree using ‘FINISHTIME’. Once we have built a segment tree, for each query calculate the range minimum for the given range i.e. for elements between ‘Lth’ and ‘Rth’ index.
Store the result of each query in an array and return the array.
Algorithm:
- Build the minimum segment tree using ‘FINISHTIME’, the given array, and store the segment tree in a variable named ‘RANGEQUERY’.
- Initialize the answer array ‘ANS’ with size ‘Q’, that is the number of queries.
- For the ith query, store the range minimum between ‘L’ and ‘R’ in ‘ANS[ i ]’.
- Return “ANS”.
Similar problems