Hey folks,

Today we are going to learn about methods to find the minimum element in given range for an array, this problem is popularly known as range minimum query. First let us see, what are we looking at :

Given an array say **A[0,N-1]**, we are queried for the minimum element from some index ‘i’ to the index ‘j’ such that j>=i, the notation for rest of the post for this will be **RMQ(i,j)** s.t. j>=i.

Ex: A = [3 , 2 , -1 , 4 , 2]

RMQ(0,2) = -1

RMQ(3,4) = 2

RMQ(0,4) = -1

1. **Naive’s Approach **

Time Complexity : construction O(1) , Query O(N) **<O(1),O(N)>**

The idea is simple and straight forward, what we do is nothing but trivially search for the minimum from index ‘i’ to index ‘j’ by actually traversing the array between the indices. The worst case time complexity for the array traversal may be **O(N)**.

#include <cstdio>
int RMQ(int A[],int s,int e){
int minindex = s;
for(int i=s;i<=e;i++)
if(A[i]<A[minindex])
minindex = i;
return A[minindex];
}
// driver programme
int main(){
int A[10] = {3,1,2,-1,5,4,6,0,9,8};
int s,e;
scanf("%d %d",&s,&e);
printf("%d\n",RMQ(A,s,e));
return 0;
}

2. ** Dynamic Programming Approach 1 (Trivial)**

Time Complexity : Construction O(N^2) , Query O(1) **<O(N^2),O(1)>**

Writing recursion for the given problem is no big task.

j, if A[j] < A[RMQ(i,j-1)]
RMQ(i,j)=
RMQ(i,j-1), otherwise

The recursion can easily be memoized by using a two dimensional array of N*N and can be written as:

j, if A[j] < A[M[i][j-1]]
M[i][j]=
M[i][j-1], otherwise

#include <cstdio>
#define MAXN 100
int M[MAXN][MAXN];
int RMQ_DP(int A[],int N){
for(int i=0;i<N;i++)
M[i][i]=i;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
if(A[M[i][j-1]]>A[j])
M[i][j]=j;
else
M[i][j]=M[i][j-1];
}
}
}
// driver programme
int main(){
int A[10] = {3,1,2,-1,5,4,6,0,9,8};
RMQ_DP(A,10);
int s,e;
scanf("%d %d",&s,&e);
printf("%d\n",A[M[s][e]]);
return 0;
}

3. ** Split and Query **

Time Complexity : construction O(N) , Query O(sqrt(N)) **<O(N),O(sqrt(N))>**

Here we split the array in sqrt(N) equal parts of size sqrt(N), The idea is to store the minimum of each part in the an another array say M(0*sqrt(N)), and then for every query we traverse the array ‘M’ and the remaining elements of the array A.

Let us understand through an example :

A = [2,4,3,1,6,7,8,9,1,7]

image credits: TC

as it is clear from the image that M[0] is storing the index of the minimum element from A[0] to A[2] then M[1] will store index of the minimum element from A[3] to A[5] … ans so on till it is M[3] which will store A[9] as there are no further elements.

#include <cstdio>
#include <cmath>
#define MAXN 100
int M[MAXN];
/* M[i] = the index of the minimum element from A[i*sqrt(N)] to A[i*sqrt(N)+sqrt(N)-1] */
int size_m; // stores the size of the M array
void RMQ_SPLIT(int A[],int N){
size_m =0;
for(int i=0;i<N;){
int minindex = i;
for(int j=0;j<(int)sqrt(N) && i<N;j++){
if(A[i]<A[minindex])
minindex=i;
i++;
}
M[size_m++]=minindex;
}
}
int RMQ(int A[],int s,int e,int N){
int start = s/(int)sqrt(N); // this will compute the starting index of the M array
int ans = A[s];
int end = e/(int)sqrt(N); // ending index of the M array
for(int i=s;i<(start+1)*sqrt(N);i++)
if(A[i]<ans)
ans = A[i];
for(int i=start+1;i<end;i++){
if(A[M[i]]<ans)
ans=A[M[i]];
}
for(int i=end*sqrt(N);i<=e;i++){
if(A[i]<ans)
ans = A[i];
}
return ans;
}
// driver programme
int main(){
int A[10] = {3,1,2,-1,5,4,6,0,9,8};
RMQ_SPLIT(A,10);
printf("\n");
int s,e;
scanf("%d %d",&s,&e);
printf("%d\n",RMQ(A,s,e,10));
return 0;
}

4. ** Dynamic Programming Approach 2 (Sparse Table) **

Time Complexity : Construction O(NlogN) Query O(1) **<O(NlogN),O(1)>**

To get an asymptotically faster time bound, we need to think something out of the box then to just look into the trivial comparisons based algorithms. The next algorithm will take use of a special data structure known as Sparse Tables. Sparse tables stores the information from one index ‘i’ to the some index ‘j’ which is at a specific distance from ‘i’.

Here we use Sparse table to store the minimum of the elements between index ‘i’ to i+’2^j’. It can be better understood with the help of an example :

let us say, A = [2,4,3,1,6,7,8,9,1,7]

and the sparse table be two dimensional Array M( N*(log(N)+1) )

To compute M[i][j] we use dynamic programming

M[i][j-1] if(A[M[i][j-1]]<= A[M[i+2^(j-1)-1][j-1]])
M[i][j] =
M[i+2^(j-1)-1][j-1]

Now after precomputation of the table ‘M’ The RMQ can be solved in O(1) as follows :

let k = log(j-i+1)

A[M[i][k]] if(A[M[i][k]]<=A[M[j-2^k+1][k]])
RMQ(i,j) =
A[M[j-2^k+1][k]]

#include <cstdio>
#define MAXN 1000
#define MAXLOGN 10
int M[MAXN][MAXLOGN];
void Compute_ST(int A[],int N){
int i,j;
for(i=0;i<N;i++)
M[i][0]=i;
for(j=1;1<<j <=N ;j++){
for(i=0;i+(1<<(j-1))<N;i++){
if(A[M[i][j-1]]<=A[M[i+(1<<(j-1))][j-1]])
M[i][j]=M[i][j-1];
else
M[i][j]=M[i+(1<<(j-1))][j-1];
}
}
}
int RMQ(int A[],int s,int e){
int k=e-s;
k=31-__builtin_clz(k+1); // k = log(e-s+1)
if(A[M[s][k]]<=A[M[e-(1<<k)+1][k]])
return A[M[s][k]];
return A[M[e-(1<<k)+1][k]];
}
// driver programme
int main(){
int A[10] = {3,1,2,-1,5,4,6,0,9,8};
Compute_ST(A,10);
int s,e;
scanf("%d %d",&s,&e);
printf("%d\n",RMQ(A,s,e));
return 0;
}

5. **Segment Trees**

Time Complexity : Construction O(N) Query O(logN) **<O(N),O(logN)>**

segment tree are one of the most popular and most powerful data structures for interval update and interval queries. Segment trees are mostly preferred over any other methods described above and are useful in most of the programming competitions. Segment trees are heap like data structures. The segment tree for an array of size 10 would look like this.

Segment tree can be stored in the form of an array of size ‘2^(logN+1)-1’ say M.The left and the right child of node numbered ‘x’ will be ‘2*x+1’ and ‘2*x+2’ respectively.

#include <cstdio>
#define MAXN 1000
#define MAXSIZE 10000
int M[MAXSIZE];
//node is the index of the segment tree m, start and end are the index of the the array A
void BuildTree(int node,int start,int end,int A[],int N){
if(start==end)
M[node]=start;
else{
BuildTree(2*node+1,start,(start+end)/2,A,N);
BuildTree(2*node+2,(start+end)/2+1,end,A,N);
if(A[M[2*node+1]]<A[M[2*node+2]])
M[node]=M[2*node+1];
else
M[node]=M[2*node+2];
}
}
int RMQ(int node,int start,int end,int s,int e,int A[]){
if(s<=start && e>=end)
return M[node];
else if(s>end || e<start)
return -1;
int q1 = RMQ(2*node+1,start,(start+end)/2,s,e,A);
int q2 = RMQ(2*node+2,(start+end)/2+1,end,s,e,A);
if(q1==-1)
return q2;
else if(q2==-1)
return q1;
if(A[q1]<A[q2])
return q1;
return q2;
}
// driver programme
int main(){
int A[10] = {3,1,2,-1,5,4,6,0,9,8};
BuildTree(0,0,10-1,A,10);
int s,e;
scanf("%d %d",&s,&e);
printf("%d\n",A[RMQ(0,0,10-1,s,e,A)]);
return 0;
}

Now, out of the five approaches last two are generally preferred for most of the programming competitions. Segment trees are more popular, because they are more flexible than sparse tables, they can also be used for interval update which is most often clubbed with the interval query in a programming challenges while sparse table can not be used to update the array(as it is based on precomputations).

**External Links:**

Topcoder Tutorial on RMQ and LCA

Codechef Problem

Sparse Table Solution for the Above Problem

SPOJ Problem BRCKTS

SPOJ Problem GSS3

Spoj Problem HORRIBLE

SPOJ problem GSS2

SPOJ problem SEGSQRSS

SPOJ problem ORDERSET

return 42;