Question

Given n arrays, each array contain n positive integers. Write an O(n² log(n)) algorithm to find the smallest n sums out of nⁿ possible sums that can be obtained by picking one positive integer from each of n arrays. For example, given three arrays as follows: [5, 1, 8] , [5, 2, 9] , and [6, 7, 10]. The smallest n sums of the given array is [9, 10, 12].

Answer 1

To find the smallest n sums out of nⁿ possible sums, we can use a combination of sorting and heap data structure.

Step-by-step explanation:

To find the smallest n sums out of nⁿ possible sums, we can use a combination of sorting and heap data structure. Here is an O(n² log(n)) algorithm:

1. Create an empty min-heap and insert the first element from each array into the heap.
2. Repeat the following n times:
   1. Extract the minimum element from the heap and add it to the result list.
   2. Replace the extracted element with the next element from its respective array.
   3. If the array still has elements, insert the new element into the heap.

The result list will contain the smallest n sums of the given arrays. In the example you provided, the smallest n sums are [9, 10, 12].