Range Minimum Query

Hard
0/120
profile
Contributed by
6 upvotes
Asked in companies
Media.netAccolite

Problem statement

You are given an array ‘ARR’ consisting of ‘N’ integers. You have to process ‘Q’ queries, in each query, you will be provided two integers ’L’ and ‘R’, and find the minimum array element in the range [L, R].

Note : 
L and R in each query follow 0-based indexing.
Follow up: 
For each query, do it faster than linear time.
For Example : 
If N = 7, ARR = {1, 2, 3, 4, 3, 2, 1}, Q = 2 and Queries = { {0, 3}, {3, 5} }

For the first query, we need to find the smallest number between the Arr[0], Arr[1], Arr[2] and Arr[3], clearly, the smallest number is Arr[0] = 1, so we will print 1.
For the second query, we need to find the smallest number amongst Arr[3], Arr[4] and Arr[5], clearly, the smallest number is Arr[5] = 2, so we will print 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the number of elements in the array.

The second line of each test case contains N integers ‘ARR’, denoting the array elements.

The third line of each test case contains a single integer ‘Q’, denoting the number of queries.

The next Q lines, each contain two integers ‘L’ and ‘R’, denoting the left end and the right end of the range.
Output Format : 
For each test case, print the smallest element in the range [L, R].

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ N ≤ 1000  
0 ≤ Arr[i] ≤ 10^9
1 ≤ Q ≤ 50
0 ≤ L ≤ R < N

Time limit: 1 sec
Sample Input 1 :
2
7
1 2 3 4 3 2 1
2
0 3
3 5
4
1 3 1 2
3
0 3
1 1
1 2
Sample Output 1 :
1
2
1
3
1
Explanation For Sample Input 1 :
For test case 1 :
For the first query, we need to find the smallest number between the Arr[0], Arr[1], Arr[2] and Arr[3], clearly, the smallest number is Arr[0] = 1, so we will print 1.
For the second query, we need to find the smallest number amongst Arr[3], Arr[4] and Arr[5], clearly, the smallest number is Arr[5] = 2, so we will print 2.

For test case 2 : 
For the first query, we need to find the smallest number between the Arr[0], Arr[1], Arr[2] and Arr[3], clearly, the smallest number is Arr[0] = 1, so we will print 1.
For the second query, there is only one element in the range so the minimum element itself is Arr[1] = 3, so we will print 3.
For the third query, we need to find the smallest number amongst Arr[1] and Arr[2], clearly, the smallest number is Arr[2] = 1, so we will print 1.
Sample Input 2 :
2
1
1
1
0 0
5
1 5 3 4 5
1
1 3
Sample Output 2 :
1
3
Hint

Simply process each query one at a time.

Approaches (2)
Brute Force

For each query iterate all the elements in the range [L, R] and return the minimum element.

 

The steps are as follows :

  1. Declare ‘ans’ array to store the minimum element of each query.
  2. Process each query one at a time, for each query initialize a variable ‘minElement’ equal to INT_MAX, now simply iterate the range [L, R] using a FOR loop and store the minimum element of this range in ‘minElement’. Insert the ‘minElement’ in ‘ans’.
  3. Finally, return ‘ans’ array.
Time Complexity

O( Q * N ), where Q and N denote the number of queries and size of the array respectively.

 

For each query, in the worst case, we will traverse ~N array elements, and we might have to process Q such queries.

Hence the time complexity is O( Q*N ).

Space Complexity

O( 1 )

 

No auxiliary space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Range Minimum Query
Full screen
Console