# algorithm - with - sort two arrays based on one c++

## Efficiently get sorted sums of a sorted list (4)

If you write out the sums like this:

```
1 4 5 6 8 9
---------------
2 5 6 7 9 10
8 9 10 12 13
10 11 13 14
12 14 15
16 17
18
```

You'll notice that since M[i,j] <= M[i,j+1] and M[i,j] <= M[i+1,j], then you only need to examine the top left "corners" and choose the lowest one.

e.g.

- only 1 top left corner, pick 2
- only 1, pick 5
- 6 or 8, pick 6
- 7 or 8, pick 7
- 9 or 8, pick 8
- 9 or 9, pick both :)
- 10 or 10 or 10, pick all
- 12 or 11, pick 11
- 12 or 12, pick both
- 13 or 13, pick both
- 14 or 14, pick both
- 15 or 16, pick 15
- only 1, pick 16
- only 1, pick 17
- only 1, pick 18

Of course, when you have *lots* of top left corners then this solution devolves.

I'm pretty sure this problem is Ω(n²), because you have to calculate the sums for each M[i,j] -- unless someone has a better algorithm for the summation :)

You have an ascending list of numbers, what is the most efficient algorithm you can think of to get the ascending list of sums of every two numbers in that list. Duplicates in the resulting list are irrelevant, you can remove them or avoid them if you like.

To be clear, I'm interested in the algorithm. Feel free to post code in any language and paradigm that you like.

Rather than coding this out, I figure I'll pseudo-code it in steps and explain my logic, so that better programmers can poke holes in my logic if necessary.

On the first step we start out with a list of numbers length n. For each number we need to create a list of length n-1 becuase we aren't adding a number to itself. By the end we have a list of about n sorted lists that was generated in O(n^2) time.

```
step 1 (startinglist)
for each number num1 in startinglist
for each number num2 in startinglist
add num1 plus num2 into templist
add templist to sumlist
return sumlist
```

In step 2 because the lists were sorted by design (add a number to each element in a sorted list and the list will still be sorted) we can simply do a mergesort by merging each list together rather than mergesorting the whole lot. In the end this should take O(n^2) time.

```
step 2 (sumlist)
create an empty list mergedlist
for each list templist in sumlist
set mergelist equal to: merge(mergedlist,templist)
return mergedlist
```

The merge method would be then the normal merge step with a check to make sure that there are no duplicate sums. I won't write this out because anyone can look up mergesort.

So there's my solution. The entire algorithm is O(n^2) time. Feel free to point out any mistakes or improvements.

Well, O(n) would be a lower bound (probably not tight though), otherwise you could run the O(n) algorithm n times to get a sorted list in O(n^2).

Can you assume the two sets are sorted (you present them in sorted order above)? If so, you could possibly get something with an average case that's decently better by doing an "early out", starting at the last pair of elements, etc. Just a hunch though.

You can do this in two lines in python with

```
allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)
```

The cost of this is n^2 (maybe an extra log factor for the set?) for the iteration and s * log(s) for the sorting where s is the size of the set.

The size of the set could be as big as n*(n-1)/2 for example if X = [1,2,4,...,2^n]. So if you want to generate this list it will take at least n^2/2 in the worst case since this is the size of the output.

However if you want to select the first k elements of the result you can do this in O(kn) using a selection algorithm for sorted X+Y matrices by Frederickson and Johnson (see here for gory details). Although this can probably be modified to generate them online by reusing computation and get an efficient generator for this set.

@deuseldorf, Peter There is some confusion about (n!) I seriously doubt deuseldorf meant "n factorial" but simply "n, (very excited)!"