maximum sum combination

This problem was a real real pain, from the logic right to the debugging part. I really missed the idea of using heapq because maybe I was thinking of comparing the values manually but I should have known that it wouldn't work cause was too complicated. 

But after all I thought of using the heapq and realised that it will work... everything is fine until I used a LIST to check that I don't consider the combinations twice, but the biggest problem with lists is that they offer O(n) for 'in' and 'not in' operators, I didn't even know this ;( and it took me like 24 minutes bcz the code was obviously not out of bound in terms of the time complexity but there was a TLE, I could only pass 1010 cases somewhat.

Then the 'sets' came in into play, I got to know that sets use 'Hash Tables' under the hood, and this is really amazing cause they offer O(1) for almost all the operations which was all I needed.

Finally, the code worked! 

                                                                                    Exactly ;)

Also if I were using C++ for this I would have had to use Priority Queues, but I didn't go for that cause that's just too much unnecessary code.

The logic is quite tricky but I think the comments should alleviate that...maybe.

Problem Statement:-

Given two integer array A and B of size N each.
A sum combination is made by adding one element from array A and another element of array B.
Return the maximum K valid sum combinations from all the possible sum combinations.

Note : Output array must be sorted in non-increasing order.

Example 1:

Input:
N = 2
K = 2
A [ ] = {3, 2}
B [ ] = {1, 4}
Output: {7, 6}
Explanation: 
7 -> (A : 3) + (B : 4)
6 -> (A : 2) + (B : 4)

Example 2:

Input:
N = 4
K = 3
A [ ] = {1, 4, 2, 3}
B [ ] = {2, 5, 1, 6}
Output: {10, 9, 9}
Explanation: 
10 -> (A : 4) + (B : 6)
9 -> (A : 4) + (B : 5)
9 -> (A : 3) + (B : 6)

Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCombinations() which takes the interger N,integer K and two integer arrays A [ ] and B [ ] as parameters and returns the maximum K valid distinct sum combinations .

Expected Time Complexity: O(Nlog(N))
Expected Auxiliary Space: O(N)

Constraints:
1 ≤ N ≤  105
1 ≤ K ≤  N
1 ≤ A [ i ] , B [ i ] ≤ 104

Code Implementation:-

Note: The code will give a TLE if  we use done_combs as a list instead of set. 

Because then the loop which runs k times gets a O(n) extra for each iteration, that makes it O(k*n)

and when k is n( which it can be in worst case scenario ) the overall complexity will become O(n^2).

And that's BAD....

import heapq as HP

class Solution:

    def maxCombinations(self, n, k, A, B):

        # Code here

        A.sort()

        B.sort()

        ans=[]

       

        # the combinations that are considered, and won't consider them again

        done_combs=set()

       

        # To make this a heap and get the largest sums using heapq

        arr=[]

        # makes the arr a heap inplace, the heap structure will help us to

        # get the largest sums easily

        HP.heapify(arr)

       

        '''

         basically for k times, will be considering all the possibilities,

         for example if we just considered ith elem from A, and jth elem from B

         1) then next will consider i-1th elem from A with jth elem from B

         2) and will consider ith elem from A with j-1th elem from B

        '''

       

        # will store the sums alongwith the indices, so that later can consider the

        # further cases,

       

        '''

         also, will be storing sums in their negative form, bcz heapq keeps the

         arr in ascending, order,

         so to get the arr in the descending order, will store their negatives

         like instead of storing [1,2,3,4,5] will store [-1,-2,-3,-4,-5],

         so the heapq will give us 1 in the first type of array and -5 in the 2nd one

        '''

        HP.heappush(arr, ( -A[n-1]-B[n-1],(n-1,n-1) ) )

        done_combs.add((n-1,n-1))

       

        for _ in range(k):

           

            best=HP.heappop(arr)

            # best=(1,(1,1))

            # adding the summation to the ans array

            ans.append(0-best[0])

            # adding the indices so they are not repeated

            # done_combs.add(best[1])

           

            # print(best)

           

            i=best[1][0]

            j=best[1][1]

           

            # dp[i][j]=1

            # if(i==0 or j==0):

            #     return ans

           

            if((i-1,j) not in done_combs):

                done_combs.add((i-1,j))

                HP.heappush(arr,( -A[i-1]-B[j] ,(i-1,j)))

               

            if((i,j-1) not in done_combs):

                done_combs.add((i,j-1))

                HP.heappush(arr, ( -A[i]-B[j-1] ,(i,j-1) ) )

            # now just repeat this for k times, bcz everytime will get a max sum

           

        # print(ans)

        return ans

fsfsf