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 distinct sum combinations from all the possible sum combinations.
Note : Output array must be sorted in non-increasing order.
Example 1:
Input:
N = 2
C = 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
C = 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(Klog(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤  10^{5}
1 ≤ K ≤  N
1 ≤ A [ i ] , B [ i ] ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def maxCombinations(self, N, K, A, B):

        # Code here

Solutions:
class Solution:

	def maxCombinations(self, n, K, a, b):
		import heapq
		a.sort()
		b.sort()
		n = len(a)
		pq = []
		heapq.heapify(pq)
		pq.append((-a[n - 1] - b[n - 1], (n - 1, n - 1)))
		my_set = set()
		my_set.add((n - 1, n - 1))
		for count in range(K):
			temp = heapq.heappop(pq)
			print(-temp[0], end=' ')
			i = temp[1][0]
			j = temp[1][1]
			sum = a[i - 1] + b[j]
			temp1 = (i - 1, j)
			if temp1 not in my_set:
				heapq.heappush(pq, (-sum, temp1))
				my_set.add(temp1)
			sum = a[i] + b[j - 1]
			temp1 = (i, j - 1)
			if temp1 not in my_set:
				heapq.heappush(pq, (-sum, temp1))
				my_set.add(temp1)
		return []


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		pq = []
		A.sort(reverse=True)
		B.sort(reverse=True)
		ans = []
		heapq.heappush(pq, (-A[0] - B[0], 0, 0))
		marked = set()
		while len(ans) < K:
			(d, i, j) = heapq.heappop(pq)
			ans.append(-d)
			if j + 1 < N and (not i * N + j + 1 in marked):
				marked.add(i * N + j + 1)
				heapq.heappush(pq, (-A[i] - B[j + 1], i, j + 1))
			if i + 1 < N and (not (i + 1) * N + j in marked):
				marked.add((i + 1) * N + j)
				heapq.heappush(pq, (-A[i + 1] - B[j], i + 1, j))
		return ans


class Solution:

	def maxCombinations(self, n, K, a, b):
		import heapq
		pq = []
		ans = []
		A.sort()
		B.sort()
		heapq.heappush(pq, (-a[n - 1] - b[n - 1], (n - 1, n - 1)))
		st = set()
		st.add((n - 1, n - 1))
		for count in range(K):
			temp = heapq.heappop(pq)
			ans.append(-temp[0])
			i = temp[1][0]
			j = temp[1][1]
			sum = a[i - 1] + b[j]
			temp1 = (i - 1, j)
			if temp1 not in st:
				heapq.heappush(pq, (-sum, temp1))
				st.add(temp1)
			sum = a[i] + b[j - 1]
			temp1 = (i, j - 1)
			if temp1 not in st:
				heapq.heappush(pq, (-sum, temp1))
				st.add(temp1)
		return ans


import heapq

class Solution:

	def maxCombinations(self, n, k, a, b):
		ans = []
		a.sort()
		b.sort()
		s_set = set()
		hp = [[-(a[n - 1] + b[n - 1]), (n - 1, n - 1)]]
		while k > 0:
			p = heapq.heappop(hp)
			if p[1] not in s_set:
				ans.append(-p[0])
				x1 = p[1][0] - 1
				y1 = p[1][1]
				x2 = p[1][0]
				y2 = p[1][1] - 1
				heapq.heappush(hp, [-(a[x1] + b[y1]), (x1, y1)])
				heapq.heappush(hp, [-(a[x2] + b[y2]), (x2, y2)])
				k -= 1
			s_set.add(p[1])
		return ans


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort()
		B.sort()
		maxHeap = [(-A[N - 1] - B[N - 1], N - 1, N - 1)]
		heapq.heapify(maxHeap)
		mySet = set()
		res = []
		while K > 0:
			(sum, x, y) = heapq.heappop(maxHeap)
			res.append(-sum)
			if (x - 1, y) not in mySet:
				heapq.heappush(maxHeap, (-A[x - 1] - B[y], x - 1, y))
				mySet.add((x - 1, y))
			if (x, y - 1) not in mySet:
				heapq.heappush(maxHeap, (-A[x] - B[y - 1], x, y - 1))
				mySet.add((x, y - 1))
			K -= 1
		return res


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		return self.find_max_sum(A, B, K, N)

	def find_max_sum(self, arr1, arr2, req_no_of_items, total_size):
		arr1.sort(reverse=True)
		arr2.sort(reverse=True)
		max_sum_combinations = []
		heap = []
		arr1_index = 0
		arr2_index = 0
		index_valid_set = set()
		curr_sum = (arr1[arr1_index] + arr2[arr2_index]) * -1
		heapq.heappush(heap, (curr_sum, arr1_index, arr2_index))
		while len(max_sum_combinations) < req_no_of_items and len(heap):
			(max_val, index1, index2) = heapq.heappop(heap)
			max_sum_combinations.append(max_val * -1)
			if index1 + 1 < total_size and (index1 + 1, index2) not in index_valid_set:
				next_sum = (arr1[index1 + 1] + arr2[index2]) * -1
				index_valid_set.add((index1 + 1, index2))
				heapq.heappush(heap, (next_sum, index1 + 1, index2))
			if index2 + 1 < total_size and (index1, index2 + 1) not in index_valid_set:
				next_sum = (arr1[index1] + arr2[index2 + 1]) * -1
				index_valid_set.add((index1, index2 + 1))
				heapq.heappush(heap, (next_sum, index1, index2 + 1))
		return max_sum_combinations

	def heap_push(self, new_val, heap):
		heap.append(new_val)
		curr_index = len(heap) - 1
		while curr_index > 0 and heap[(curr_index - 1) // 2][0] < heap[curr_index][0]:
			parent_index = (curr_index - 1) // 2
			(heap[curr_index], heap[parent_index]) = (heap[parent_index], heap[curr_index])
			curr_index = parent_index
		return

	def heap_pop(self, heap):
		(heap[0], heap[-1]) = (heap[-1], heap[0])
		max_val = heap.pop()
		self.max_heapify(0, heap, len(heap))
		return max_val

	def max_heapify(self, parent_index, heap, heap_size):
		while 2 * parent_index + 1 < heap_size:
			largest_val_index = 0
			left_child_index = 2 * curr_index + 1
			right_child_index = 2 * curr_index + 2
			if right_child_index >= heap_size:
				largest_val_index = left_child_index
			else:
				largest_val_index = left_child_index if heap[left_child_index][0] > heap[right_child_index][0] else right_child_index
			if heap[parent_index][0] < heap[largest_val_index][0]:
				(heap[parent_index], heap[largest_val_index]) = (heap[largest_val_index], heap[parent_index])
				parent_index = largest_val_index
			else:
				break
		return


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort()
		B.sort()
		res = []
		heapq.heappush(res, (-A[N - 1] - B[N - 1], (N - 1, N - 1)))
		se = set()
		se.add((N - 1, N - 1))
		result = []
		while K:
			data = heapq.heappop(res)
			result.append(-data[0])
			(i, j) = (data[1][0], data[1][1])
			su = -A[i - 1] - B[j]
			temp = (i - 1, j)
			if temp not in se:
				heapq.heappush(res, (su, temp))
				se.add(temp)
			su = -A[i] - B[j - 1]
			temp = (i, j - 1)
			if temp not in se:
				heapq.heappush(res, (su, temp))
				se.add(temp)
			K -= 1
		return result


class Solution:

	def maxCombinations(self, N, K, A, B):
		import heapq
		pq = []
		ans = []
		A.sort()
		B.sort()
		for i in range(N):
			heapq.heappush(pq, (-1 * (A[i] + B[N - 1]), (i, N - 1)))
		while pq and K > 0:
			ele = heapq.heappop(pq)
			val = ele[0] * -1
			(x, y) = (ele[1][0], ele[1][1])
			if y != 0:
				heapq.heappush(pq, (-1 * (A[x] + B[y - 1]), (x, y - 1)))
			ans.append(val)
			K -= 1
		return ans


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort()
		B.sort()
		ans = []
		pq = []
		for i in range(N):
			heapq.heappush(pq, (-(A[i] + B[N - 1]), i, N - 1))
		while pq and K > 0:
			(vl, i, N) = heapq.heappop(pq)
			ans.append(-vl)
			if N > 0:
				heapq.heappush(pq, (-(A[i] + B[N - 1]), i, N - 1))
			K -= 1
		return ans


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort(reverse=True)
		B.sort(reverse=True)
		vis = set()
		(res, ans) = ([], [])
		heapq.heappush(res, (-(A[0] + B[0]), (0, 0)))
		while K > 0:
			(total, cordi) = heapq.heappop(res)
			(x, y) = cordi
			if (x, y) not in vis:
				vis.add((x, y))
				ans.append(-total)
				K -= 1
				xA = x + 1
				xB = y
				yA = x
				yB = y + 1
				if xA < N and xB < N:
					heapq.heappush(res, (-(A[xA] + B[xB]), (xA, xB)))
				if yA < N and yB < N:
					heapq.heappush(res, (-(A[yA] + B[yB]), (yA, yB)))
		return ans


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort()
		B.sort()
		heap = []
		ans = []
		s = set()
		maxSum = A[-1] + B[-1]
		maxSumIndexPair = (len(A) - 1, len(B) - 1)
		maxSumElem = (-maxSum, maxSumIndexPair)
		heapq.heappush(heap, maxSumElem)
		while len(ans) < K:
			elem = heapq.heappop(heap)
			newMaxSum = -elem[0]
			indicesPair = elem[1]
			if indicesPair not in s:
				s.add(indicesPair)
				ans.append(newMaxSum)
				if indicesPair[0] > 0:
					a_index = indicesPair[0] - 1
					b_index = indicesPair[1]
					pair = (a_index, b_index)
					if pair not in s:
						possibleMaxSum = A[a_index] + B[b_index]
						possibleMaxSumElem = (-possibleMaxSum, pair)
						heapq.heappush(heap, possibleMaxSumElem)
				if indicesPair[1] > 0:
					a_index = indicesPair[0]
					b_index = indicesPair[1] - 1
					pair = (a_index, b_index)
					if pair not in s:
						possibleMaxSum = A[a_index] + B[b_index]
						possibleMaxSumElem = (-possibleMaxSum, pair)
						heapq.heappush(heap, possibleMaxSumElem)
		return ans


from queue import PriorityQueue
import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort()
		B.sort()
		ans = []
		pq = []
		for i in range(N):
			heapq.heappush(pq, (-(A[i] + B[N - 1]), i, N - 1))
		while pq and K > 0:
			(vl, x, y) = heapq.heappop(pq)
			ans.append(-vl)
			if y > 0:
				heapq.heappush(pq, (-(A[x] + B[y - 1]), x, y - 1))
			K -= 1
		return ans


import heapq

class Solution:

	def maxCombinations(self, N, K, A, B):
		A.sort(reverse=True)
		B.sort(reverse=True)
		res = []
		heap = []
		heap.append((A[0] + B[0], 0, 0))
		heapq._siftdown_max(heap, 0, len(heap) - 1)
		s = set()
		for i in range(K):
			p = heapq._heappop_max(heap)
			res.append(p[0])
			(m, n) = (p[1], p[2])
			if m + 1 < N and (m + 1, n) not in s:
				heap.append((A[m + 1] + B[n], m + 1, n))
				heapq._siftdown_max(heap, 0, len(heap) - 1)
				s.add((m + 1, n))
			if n + 1 < N and (m, n + 1) not in s:
				heap.append((A[m] + B[n + 1], m, n + 1))
				heapq._siftdown_max(heap, 0, len(heap) - 1)
				s.add((m, n + 1))
		return res