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