By PRIYA KUMARI
Given module finds the minimum element in an array between position i to j. RMQ can be used in problems directly or can be applied to implement other task like the Lowest Common Ancestor problem.
-->Description of the method used
1. buildTable
Parameters :- buildtable(arr,n).
Description: This method is to build the sparse table which accepts data in array form which is 1-based indexing (it should have n+1 elements and 0th index can have any value which you don't want to consider).
2. query:-
Parameters:-query (sparseTable,i,j)
Description:-This method iterate and give result in O(log n)
3. optimisedRMQ :-
Parameters:-optimisedRMQ(sparseTable,i,j)
Description:-It finds the maximum and minimum element present in the array in O(1).
-->How to use
Create a new file where you want to use the module, and just write the code
then to test the code:-
1) Create the array in which you want to find the minimum element.
2) Build the sparse table by calling the method buildTable.
3) Print the minimum element in the table using the method optimisedRMQ.
O(Nlogā”N)">O(NlogN).
Submitted by PRIYA KUMARI (priyaCode25)
Download packets of source code on Coders Packet
Comments