23

I'm presenting a problem my professor showed in class, with my O(n*log(n)) solution:

Given a list of n numbers we'd like to perform the following n-1 times:

  • Extract the two minimal elements x,y from the list and present them
  • Create a new number z , where z = x+y
  • Put z back into the list

Suggest a data structure and algorithm for O(n*log(n)) , and O(n)

Solution:

We'll use a minimal heap:

Creating the heap one time only would take O(n). After that, extracting the two minimal elements would take O(log(n)). Placing z into the heap would take O(log(n)).

Performing the above n-1 times would take O(n*log(n)), since:

O(n)+O(n∙(logn+logn ))=O(n)+O(n∙logn )=O(n∙logn )

But how can I do it in O(n)?

EDIT:

By saying: "extract the two minimal elements x,y from the list and present them ", I mean printf("%d,%d" , x,y), where x and y are the smallest elements in the current list.

16
  • Just to make sure it's clear: you want to reduce the array to a single element, each step removing the 2 minimal elements and injecting back their sum, and you want to do this in O(n) time?
    – cheeken
    Jun 19, 2012 at 0:35
  • Do you know anything about the sizes of the numbers in the list? Are they guaranteed to be within some range? Jun 19, 2012 at 0:49
  • 7
    There's no way you could have misunderstood the problem, is there? :) My kneejerk reaction is to say this is impossible. Clearly, you need to iterate over the array (n-1) times, which means you'll be peforming some operation on the scale of O(n) times. To achieve an overall O(n) time, you'd need that operation to be O(1). You can find the two minimum values in O(1) time in a sorted list, but injecting a value back into the list and maintaining the sort would be log(n). Unless you want to get into radix sort, but that's a bit fishy.
    – cheeken
    Jun 19, 2012 at 0:49
  • +1 To the question anyway, my curiosity is piqued. :)
    – cheeken
    Jun 19, 2012 at 0:51
  • 8
    Proof of cheeken's kneejerk reaction: Suppose you can do this. Suppose further that when you insert z into the list, you stick a flag on it to say "this is a computed value, not an original value". Suppose finally that when you present the numbers, you only print out the ones with the flag unset. Then you have sorted your list of numbers in O(n). Therefore, some kind of skullduggery is required, such as for example radix sort on fixed-size integers. Jun 19, 2012 at 0:52

4 Answers 4

12

This is not a full answer. But if the list was sorted, then your problem is easiy doable in O(n). To do it, arrange all of the numbers in a linked list. Maintain a pointer to a head, and somewhere in the middle. At each step, take the top two elements off of the head, print them, advance the middle pointer until it is where the sum should go, and insert the sum.

The starting pointer will move close to 2n times and the middle pointer will move about n times, with n inserts. All of those operations are O(1) so the sum total is O(n).

In general you cannot sort in time O(n), but there are a number of special cases in which you can. So in some cases it is doable.

The general case is, of course, not solvable in time O(n). Why not? Because given your output, in time O(n) you can run through the output of the program, build up the list of pairwise sums in order as you go, and filter them out of the output. What is left is the elements of the original list in sorted order. This would give a O(n) general sorting algorithm.

Update: I was asked to show how could you go from the output (10, 11), (12, 13), (14, 15), (21, 25), (29, 46) to the input list? The trick is that you always keep everything in order then you know how to look. With positive integers, the next upcoming sum to use will always be at the start of that list.

Step 0: Start
  input_list: (empty)
  upcoming sums: (empty)

Step 1: Grab output (10, 11)
  input_list: 10, 11
  upcoming_sums: 21

Step 2: Grab output (12, 13)
  input_list: 10, 11, 12, 13
  upcoming_sums: 21, 25

Step 3: Grab output (14, 15)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sums: 21, 25, 29

Step 4: Grab output (21, 25)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 29, 46

Step 5: Grab output (29, 46)
  input_list: 10, 11, 12, 13, 14, 15
  upcoming_sum: 75
13
  • Ah, very nice! Surely this plays a part in the solution the professor has in mind.
    – cheeken
    Jun 19, 2012 at 3:15
  • Is that possible to do something like that in Python?
    – Akavall
    Jun 19, 2012 at 3:54
  • @Akavall it is easy to make a linked list in Python, see stackoverflow.com/questions/280243/python-linked-list for several examples. It is, however, going to have a bad constant, so in practice people generally don't go that way.
    – btilly
    Jun 19, 2012 at 4:15
  • If you allow for the time required to sort, this is an alternate (and possibly, more straightforward) O(n*log(n)) solution, too.
    – Novak
    Jun 19, 2012 at 5:34
  • 1
    @robertking I see what you were thinking. But now that we agree on the output, you see how easy it is to generate the sums on the fly, filter them out, and get the original list back.
    – btilly
    Jun 20, 2012 at 5:02
2

This isn't possible in the general case.

Your problem statement reads that you must reduce your array to a single element, performing a total of n-1 reduction operations. Therefore, the number of reduction operations performed is on the order of O(n). To achieve a overall running time of O(n), each reduction operation must run in O(1).

You have clearly defined your reduction operation:

  • remove the 2 minimal elements in the array and print them, then
  • insert the sum of those elements into the array.

If your data structure were a sorted list, it is trivial to remove two minimal elements in O(1) time (pop them off the end of the list). However, reinserting an element in O(1) is not possible (in the general case). As SteveJessop pointed out, if you could insert into a sorted list in O(1) time, the resultant operations would constitute an O(n) sorting algorithm. But there is no such known algorithm.

There are some exceptions here. If your numbers are integers, you may be able to use "radix insert" to achieve O(1) inserts. If your array of numbers are sufficiently sparse in the number line, you may be able to deduce insert points in O(1). There are numerous other exceptions, but they are all exceptions.

This answer doesn't answer your question, per se, but I believe it's relevant enough to warrant an answer.

3
  • This is really just a repost of my and others' comments. But given that there appears to be no solution, I thought it prudent to post as an answer.
    – cheeken
    Jun 19, 2012 at 1:33
  • But even with radix sort would it's be O(n+m) where m is the number of buckets (radices? bucket sort == radix sort, but I don't know the proper terminology), m >= n since, since you don't know which buckets have data in them (and must try them all even if they're empty). And even that assuses no negative numbers. If you need to recheck old buckets, O(n + m^2)
    – acattle
    Jun 19, 2012 at 1:51
  • See my answer for the note that if the array is replaced by a linked list, then the reinsert in time O(1) is doable. However there is still an implicit sort lurking in the background.
    – btilly
    Jun 19, 2012 at 3:01
1

If the range of values is less than n, then this can be solved in O(n).

1> Create an array mk of size equal to range of values and initialize it to all zero

2> traverse through the array and increment value of mk at the position of the array element. i.e if the array element is a[i] then increment mk[a[i]]

3) For presenting the answers after each of the n-1 operations follow the following steps:

There are two cases:

Case 1 : all of a[i] are positive

        traverse through mk array from 0 to its size
        cnt = 0
        do this till cnt doesn't equal 2
          grab a nonzero element decrease its value by 1 and increment cnt by 1
        you can get two minimum values in this way
        present them 
        now do mk[sum of two minimum]++

Case 2 : some of a[i] is negative

        <still to update>
0

O(nlogn) is easy - just use a heap, treap or skiplist.

O(n) sounds tough.

https://en.wikipedia.org/wiki/Heap_%28data_structure%29
https://en.wikipedia.org/wiki/Treap
https://en.wikipedia.org/wiki/Skip_list
1
  • It'd probably be really fast with a splay tree, but that's still probably O(nlogn). Splay trees are nice in that the most recently used nodes get moved near the top of the tree. Jun 26, 2012 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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