Storing pairwise sums in linear space

The problem, as I understand it, is that we want to find the sums

a1 + b1  a1 + b2  ...  a1 + bna2 + b1  a2 + b2  ...  a2 + bn  ...      ...    ...    ...an + b1  an + b2  ...  an + bn

and print them in sorted order.The restriction is to use only O (n) memory and O (n^2 log n) time in the process.

Consider the above table as n lists (lines) of n elements each.If we sort the initial arrays so that a1 <= a2 <= ... <= an and b1 <= b2 <= ... <= bn, each list is already sorted.Now, the problem is reduced to merging n sorted lists.

To devise that, think of how to merge two sorted lists (as in MergeSort), then three lists, and so on.This extends trivially to merging n lists of length n each in n operations for each output element, for a total of O (n^3).Now, what's left is to reduce time for getting each output element down to O (log n).As you ask for a hint but not a complete solution, see if you can handle that step yourself.

In python you can something like that:

import heapqa = [2, 1, 3]b = [4, 6, 5]a.sort()b.sort()def add_to_b(x):    for v in b:        yield v + xfor v in heapq.merge(*[add_to_b(x) for x in a]):    print v

Result:

566777889

The idea is that we sort both arrays. Then adding to b an element of a defines a generator of increasing numbers. So we create n such generators and we merge them using heapq.merge. A generator, represented by add function above, at a specific time needs constant space (space needed to keep the current position in b). heapq.merge itself needs linear space. So we need linear space for the execution of the algorithm.

First sort the 2 arrays in ascending order, the time complexity is 2 * O(n*lgn), which can be also regarded as O(n*lgn). Then use a max heap with length n + 1 to maintain the minimum n sums.

How to maintain the minimum n sums? First push a1 + b1, a1 + b2, a1 + b3, ..., a1 + bn to the heap. Then for every a[i], 1 <= i < n and b[j], 0 <= j < n, push a[i] + b[j] and then pop the largest one:

for(int j=0;j<n;j++) {    heap.push_into(a[0] + b[j]);}for(int i=1;i<n;i++) {    for(int j=0;j<n;j++) {        heap.push_into(a[i] + b[j]);        heap.pop(); // remove the current largest sum in the heap, then the sums remain in the heap are the smallest n sums    }}

Then the n elements in the heap are the smallest n sums.

The time complexity is O(n^2 * lgn), space complexity is O(n).