Python O(n * log(n)) Solution


#1

By sorting two arrays, we can find the maximum as we iterate from behind; but it is possible that we have a duplicate pair. For this, we use set to avoid selecting same pairs. As well, we use max-heap to maintain the best max sum that we have.

from heapq import heapify, heappop, heappush

class Solution:
    # @param A : list of integers
    # @param B : list of integers
    # @param C : integer
    # @return a list of integers
    def solve(self, A, B, C):
        
        A.sort()
        B.sort()
        
        seen, pq, result = set(), list(), list()
        i, j = len(A) - 1, len(A) - 1
        seen.add((i,j))
        pq.append( (-(A[i] + A[j]), (i, j)) )
        for _ in range(C):
            sum, (i, j) = heappop(pq)
            result.append(-sum)
            for ni, nj in [(i-1,j), (i,j-1)]:
                if ni >= 0 and nj >= 0 and (ni, nj) not in seen:
                    heappush(pq, (-(A[ni] + A[nj]), (ni, nj)))
                    seen.add( (ni,nj) )
        
        return result