Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Great, thanks for the link. Very interesting. –  Byte May 2 '12 at 1:03
add comment

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

share|improve this answer
    
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
add comment

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))?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.