What is Range minimum query?
Sometimes we are asked to find index of minimum element within range of an array, this operation is called as range minimum query (RMQ). For example, if given array A = [2,3,4,6,8,1,5,9], ask is to find index of minimum value between index 2 and 7, returned answer would be 5.
Going by the brute force, every time a query if fired, we scan the range and find the minimum in given range in same way as we do for entire array. Complexity of each query being answered is O(N) where in worst case range is entire array.
Can we preprocess our data, so that our query operations are less costly? If we do so, there are two parts to the solution now, first, preprocessing and second query. Let’s assume complexity of each step is f(n) and g(n) respectively, then complexity of solution can be denoted as ( f(n), g(n)).
What kind of preprocessing can be done? Basic idea is to calculate minimum index of all the ranges possible in array. How many ranges are possible for an array with N elements? It’s N X N ranges. Why?
So, to store minimum index of each range, O(N2) order space is required and time complexity goes to O(N3). However, complexity of query is O(1). So overall complexity of solution is ( O(N3), O(1) ).
With application of dynamic programming, complexity of preprocessing step can be reduced to O(N2).
Can we do better for preprocessing step while trading off query step? If we divide array into smaller chunks and store minimum element index in those chunks, will it help? And what should be size of chunk? Let’s divide array in √n parts, where n is size of part.
Now, find minimum element index in each of this chunk, and store it. Extra space required is (√n). Finding minimum for each chunk has complexity of (√n * √n) as O(n).
To find minimum element index in given range, follow three steps:
1. Find minimum index of all chunks lying between start and end of given range. max √n operations 2. Find minimum index in chunk where start of range lies max √n comparisons from start of range to end of chunk. 3. Find minimum index in chuck where end of range lies from start of chunk to end of range. 4. Compare these three values and return minimum
No matter, how big or small range is to find minimum index, worst case will be O(√n) as there are only 3*√n operations.
Let’s take an example and see how it works. Find minimum in range (2,7)
To get RMQ(2,7) in the array, what are the chunks with are lying with in range, it’s just one, chunk 1. , minimum index of chunk 1 is M = 5. Now find minimum index in chunk 0 where start of range lies (starting from start of range which 2). It’s index 2. Last find minimum from start of chunk where end of range lies to end of range. It’s index 6.
At end compare A (minimum of all chunks between start and end of range ), A (minimum in chunk where start of range lies) and A (minimum in chunk where end of range lies) and we have the answer as 5 as it minimum of three.
Aggregating all thing, we found a way to optimize solution of range minimum query with complexity as ((o(n), O(√n)).
Range minimum query using sparse table
Method 3 uses only O(√n) space however query time complexity is also O(√n). To reduce query time at the expense of space, there is another method called as sparse table method. This method uses features of method 2 (dynamic programming) and feature 3 (find minimums of chunks).
In this approach, we split inout array into chunks of size 2j where j varies from 0 to log n and n is number of elements in array. There will be n log n such chunks and hence the space complexity becomes O(n log n).
After splitting, find minimum in each chunk and store it into look up table. M[i][j] stores minimum in range from i with size 2j. For example, M store minimum index between 0 and 7 (8 elements). Now problem is how to create this lookup table? This table can be created using dynamic programming from bottom up. Specifically, we find minimum in a block of size 2j by comparing the two minima of its two constituent blocks of size 2j-1. More formally,
M[i,j] = M[i, j -1] if A[M[i, j -1]] <= A[M[i+2j-1, j -1]] M[i, j] = M[i+2j-1, j -1] otherwise.
How to find minimum index in given range now? Idea is to find two sub ranges which cover the entire range and then find minimum of minimum of these two ranges. For example, find RMQ(i,j). If 2k be size of largest block that fits into the range from i to j, then k = log(j – i + 1).
Now, we have two parts to look in from i to i+2k + 1 (already computed as M[i,k] ) and from j-2k+1 (already computed as M[j-2k+1, k],).
RMQ(i,j) = M[i][k] if A[ M[i][k] ] <= A[M[j-2k+1, k]] RMQ(i,j) = M[j-2k+1, k]
These two block entirely cover the range and since only once comparison required, complexity of lookup will be O(1).
In this post we discussed various ways to implement range minimum query based on space and time complexity trade off. In future posts, we will discuss about applications of RMQ such as segmented trees and least common ancestor problem.
Please share if something is wrong or missing, we would love to hear from you.