# Algorithm for finding smallest number in a list, given list of $a$ to $b$

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

## 3 Answers

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. :)

• Great, thanks for the link. Very interesting. – Byte May 2 '12 at 1:03

you can look up "Segment tree" basically, you prepopulate a perfect binary tree that stores the minimum number of list (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (1, 2), (3, 4), (5, 6), (7, 8), (1, 4), (5, 8), (1, 8). you can do it recursively. then, if asked, what is the minimum number of, lets say (3, 7), then you just take the minimum number of list (3, 5) and (6, 7)

• the minimum number of list (3, 5) = minimum number (3, 4) and (5, 5)
• the minimum number of list (3, 4) = minimum number (3, 3) and (4, 4)
• the minimum number of list (6, 7) = minimum number (6, 6) and (7, 7)

that's it sorry if i take an angle from computer science. i'm from computer science :p

• I would give you the correct answer but Felix also have the correct answer an hour before you. Vote up for the right answer :) Thanks. Your Algorithm is O(n) precalculation and O(log n) look up right? – Byte May 2 '12 at 1:02

It sounds like the spec is: given a pair (a,b) return min(list(a),list(b))? What variable (n or m) do you think it should be linear in? Why not eliminate any preprocessing and just return min(list(a),list(b))?

• I think that the following is meant: for (a,b), with a<=b, a and b from {1,...,6}, find min{list[a], list[a+1], ... , list[b]} – miracle173 May 1 '12 at 6:32
• Yes miracle is correct about the question. – Byte May 1 '12 at 12:41