4

I'm auditing this algorithms class for work and I'm trying to do some practice problems given in class. This problem has me stumped and I just can't wrap my head around it. None of my solutions come out in O(logn) time. Can anyone help me with this problem??

Question: Suppose that we are given a sequence of n values x1, x2, ... , xn in an arbitrary order and seek to quickly answer repeated queries of the form: given an arbitrary pair i and j with 1 ≤ i < j ≤ n, find the smallest value in x1, ... , xj . Design a data structure that uses O(n) space and answers each query in O(log n) time.

Jessica Stanley
  • 309
  • 1
  • 4
  • 12
  • 1
    What's your thought process so far? – simchona Feb 21 '12 at 20:50
  • 2
    Hint: The data structure is most likely a binary tree of some sort. – Robert Harvey Feb 21 '12 at 20:50
  • So I thought of binary search trees, but I'm pretty sure that takes O(nlogn) time... unless I'm wrong. – Jessica Stanley Feb 21 '12 at 20:53
  • 1
    Bart, I'm really just sitting in on the class. In the past I've heard it referred to as auditing, that's why I used that word in particular. – Jessica Stanley Feb 21 '12 at 20:54
  • Creating the tree takes nlogn, but accessing it takes logn. I think the thing to focus on is answering the queries quickly and ensuring that the data doesn't exceed memory. – bhan Feb 21 '12 at 20:57
  • 1
    Fair enough, but regardless what your involvement is: I'm pretty sure you'll find people more willing to help if you show what you have done so far (or explain your own thoughts). – Bart Kiers Feb 21 '12 at 20:58
  • 2
    "Audire" simply means "to listen", and if you happen to be in an auditorium, it stands to reason you're auditing. :) – biziclop Feb 21 '12 at 21:01
  • My first instinct was to create two additional lists: y1...yn where yk=the smallest element between x1...xk and z1...zn where zk=the smallest element between xk...xn, but I stalled here. – biziclop Feb 21 '12 at 21:02
  • @biziclop, that technique isn't versatile enough, a small value on either end of the list would render all that preprocessing useless. The idea can be easily rectified to provide a `O(sqrt n)` time and (auxiliary) space solution. – davin Feb 21 '12 at 21:41
  • @davin Yes, that's where I was kind of stuck, I just thought it might help finding the right idea. – biziclop Feb 21 '12 at 21:49

5 Answers5

3

For input of a1,a2,a3,...an , construct a node that contains minimum of (a1,..,ak) and minimum of (ak+1,..,an) where k = n/2.

Recursively construct the rest of the tree.

Now, if you want to find the minimum between ai and aj:

  1. Identify the lowest common ancestor of i,j. Let it be k
  2. Start with i and keep moving until you hit k. AT every iteration check if the child node was left node. If yes, then compare the right subtree's min and update current min accordingly.
  3. Similarly, for j, check if it is right node....
  4. At node k compare values returned by each subtree and return the min
ElKamina
  • 7,747
  • 28
  • 43
  • 2
    Anyone who does not understand this answer can look at mine, and vice versa. They are not exactly the same, but they are very similar. I gave the picture and left out the details, while this gives the details and leaves out the picture. – btilly Feb 21 '12 at 22:36
  • @btilly, I think what this answer is talking about is a segment tree. segment tree takes O(nlogn) space, not O(logn). http://en.wikipedia.org/wiki/Segment_tree – Jack Mar 08 '12 at 01:23
  • @Jack there are 2 different data structures being called a segment tree. The one described here matches the one that wcipeg.com described, which uses O(n) space. It can be used to efficiently find the minimum value in any interval. The structure that wikipedia is describing is for the different purpose of identifying which subset of a collection of intervals contains a given point. This is why I care more about what things are than what they are called. Because different people call the same thing different things, and different things the same thing. – btilly Mar 08 '12 at 03:37
2

People are overthinking this. Suppose that you start with the list:

47, 13, 55, 29, 56, 9, 17, 48, 69, 15

Make the following list of lists:

47, 13, 55, 29, 56, 9, 17, 48, 69, 15
13,     29,     9,     17,     15
13,             9,             15
9,                             15
9

I leave the construction of these lists, correct usage, and proof that they provide an answer to the original question as exercises for the reader. (It might not be homework for you, but it could easily be for someone, and I don't like giving complete answers to homework questions.)

btilly
  • 43,296
  • 3
  • 59
  • 88
  • Does this use `O(n)` space (as required)? – ypercubeᵀᴹ Feb 21 '12 at 22:24
  • @ypercube Yes it does. And it looks like ElKamina has chosen to supply all of the details that I deliberately left missing for a slight variation of this solution. – btilly Feb 21 '12 at 22:34
  • Ah ok, I couldn't figure you were proposing that. it's not obvious that this is more like a tree structure, than a list or vertical lists. – ypercubeᵀᴹ Feb 21 '12 at 22:38
  • @ypercube Whether you think of it as a tree, a list, a vertical list, or concatenate it into a single array is a personal choice. They all work. – btilly Feb 22 '12 at 01:02
0

Trying to explain the suggested data structure:

For every pair of numbers, calculate and keep the value of the smaller one. For every four consecutive numbers, calculate and keep the value of the smallest of the four. This is done quickly by picking the smaller of the two pair values. For every eight consecutive numbers, calculate and keep the value of the smallest of the eight. And so on.

Let's say we want the smallest value of x19 to x65.

We look at the following stored values: Smallest of x32 to x63. Smallest of x24 to x31. Smallest of x20 to x23. x19. Smallest of x64 to x65.

Then we pick the smallest of these.

gnasher729
  • 51,477
  • 5
  • 75
  • 98
0

I think the crucial step is that you'll need to sort the data before hand. Then you can store the data in an array/list. Then you can run through a quick binary search in O(logn), picking out the first value that satisfies the condition (I'm assuming you meant between xi and xj, not x1 and xj).

edit: on second thought, ensuring that the value satisfies the condition may not be as trivial as I thought

bhan
  • 2,489
  • 3
  • 19
  • 26
  • 1
    How would you use a binary search for that? – biziclop Feb 21 '12 at 20:56
  • I think the instructor meant to say xi and xj as well. I copied this word for word. That would make a lot more sense, wouldn't it? :) – Jessica Stanley Feb 21 '12 at 20:57
  • If the data is already sorted, you can perform a binary search on it by adjusting the indices. IE: set a left = 0, right = length of array, mid = floor(average of left and right). Then if x < mid, adjust right to mid, and recalculate mid using the new values. – bhan Feb 21 '12 at 21:00
  • If the data is sorted, you already know the smallest element overall is the first one in your list. So all you can do is start from the first one and iterate until you find the first element with an index between i and j. This isn't O(logn) though. – biziclop Feb 21 '12 at 21:04
  • The problem is that it's in arbitrary order, though. So can it still be assumed that the data is sorted? – Jessica Stanley Feb 21 '12 at 21:06
  • @JessicaStanley The idea was to create a sorted version first, but that doesn't seem to be enough. (At least I can't see it.) – biziclop Feb 21 '12 at 21:22
0

The question was asked before in a slightly different way: What data structure using O(n) storage with O(log n) query time should I use for Range Minimum Queries?

Nevertheless, to quickly answer, the problem you're facing it's a well studied one - Range Minimum Query. A Segment Tree is a Data Structure that can solve the problem with O(N) space and O(logN) time requirements. You can see more details in here, where there's an explanation of the structure and the complexities involved.

Community
  • 1
  • 1
jace
  • 173
  • 5