Background Here is a puzzle I have been thinking over. (For some reason I believe there is a linear algorithm for this).
Question: You are given list of n numbers and a list of m pairs. You are to find out what would be the lowest number on the list for each pair.
Example: You have a list of {5,7,2,8,6,9} and list of {(1,3),(2,2),(1,5)}. Your output should be {2,7,2} assuming list number follows 1 to 6 format (not 0-5).
My best guess: Make a 2 dimensional list x being from and y being to and pre-populate the list with lowest number from x to y. Then do a linear look up on each pair. The problem is this approach will take O(n)^2 for pre-population.
So can you do better? My instinct tells me that there is an O(n) algorithm in populating the list. It might be true, but wanted to know if anyone can actually state it.
P.S. I am not sure if this or SO would be a better fit for this post. Please do move it accordingly
Best Answer
you can do that by using segment tree or range maximum/minimum query (RMQ)
Segment tree: To populate the tree the complexity is O(n) and for each query to ask what is the minimum/maximum number from x to y will take O(log n)
RMQ: to populate the array, the complexity is O(n log n) and for each query will take only O(1)
btw..log in computer science is base 2 not 10..so if I say log 16 in computer science term, then the answer is 4
which one you are going to use is depending on the number of queries requested. You can read the explanation here
http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
you don't have to read the code if you don't know how to code..but at least reading the explanation might help you get some of the idea. :)