Given an array of integers, arr[] and a number, K.You can pair two numbers of the array if the difference between them is strictly less than K. The task is to find the maximum possible sum of such disjoint pairs (i.e., each element of the array can be used at most once). The Sum of P pairs is the sum of all 2P elements of pairs.
 
Example 1:
Input  : 
arr[] = {3, 5, 10, 15, 17, 12, 9}
K = 4
Output : 
62
Explanation :
Then disjoint pairs with difference less
than K are, (3, 5), (10, 12), (15, 17)
max sum which we can get is 
3 + 5 + 10 + 12 + 15 + 17 = 62
Note that an alternate way to form 
disjoint pairs is,(3, 5), (9, 12), (15, 17)
but this pairing produces less sum.
 
Example 2:
Input  : 
arr[] = {5, 15, 10, 300}
K = 12
Output : 
25
 
Your Task:  
You don't need to read, input, or print anything. Your task is to complete the function maxSumPairWithDifferenceLessThanK() which takes the array arr[], its size N, and an integer K as inputs and returns the maximum possible sum of disjoint pairs.
 
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ K ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def maxSumPairWithDifferenceLessThanK(self, arr, N, K): 

        # Your code goes here 

Solutions:
class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		dp = [0] * N
		dp[0] = 0
		for i in range(1, N):
			dp[i] = dp[i - 1]
			if arr[i] - arr[i - 1] < K:
				if i >= 2:
					dp[i] = max(dp[i], arr[i - 1] + dp[i - 2] + arr[i])
				else:
					dp[i] = max(dp[i], arr[i] + arr[i - 1])
		return dp[N - 1]


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort(reverse=True)
		i = 0
		c = 0
		while i < N - 1:
			if arr[i] - arr[i + 1] < K:
				c += arr[i] + arr[i + 1]
				i += 2
			else:
				i += 1
		return c


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort()
		ans = 0
		i = n - 2
		j = n - 1
		while i >= 0:
			par_ans = abs(arr[i] - arr[j])
			if i == j:
				i -= 1
			elif par_ans < k:
				ans += arr[i] + arr[j]
				i -= 2
				j = i + 1
			elif par_ans >= k:
				j -= 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		sum = 0
		i = N - 1
		while i > 0:
			if abs(arr[i] - arr[i - 1]) < K:
				sum += arr[i] + arr[i - 1]
				i -= 2
			else:
				i -= 1
		return sum


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr = sorted(arr)
		result = 0
		first = None
		for i in range(N - 1, -1, -1):
			if not first:
				first = arr[i]
			elif first - arr[i] < K:
				result += first + arr[i]
				first = None
			else:
				first = arr[i]
		return result


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):

		def fun(arr, k):
			arr.sort()
			arr = arr[::-1]
			i = 0
			j = 1
			sumi = 0
			while i < len(arr) - 1 and j < len(arr):
				if arr[i] - arr[j] < k:
					sumi = sumi + arr[i] + arr[j]
					i = i + 2
					j = j + 2
				else:
					i = i + 1
					j = j + 1
			return sumi
		k = K
		return fun(arr, k)


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		res = 0
		arr = sorted(arr, reverse=True)
		i = 0
		while i < N - 1:
			if abs(arr[i] - arr[i + 1]) < K:
				res += arr[i]
				res += arr[i + 1]
				i += 2
			else:
				i += 1
		return res


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		i = 0
		ans = 0
		arr.sort()
		arr = arr[::-1]
		while i < len(arr) - 1:
			if arr[i] - arr[i + 1] < K:
				ans = ans + (arr[i] + arr[i + 1])
				i = i + 2
			else:
				i = i + 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr = sorted(arr, reverse=True)
		count = 0
		i = 0
		while i < n - 1:
			if arr[i] - arr[i + 1] < k:
				count += arr[i] + arr[i + 1]
				i += 2
			else:
				i += 1
		return count


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		sum = 0
		s = set()
		for i in range(N - 1, 0, -1):
			if i in s:
				continue
			for j in range(i - 1, -1, -1):
				if arr[i] - arr[j] < K and j not in s:
					sum += arr[i] + arr[j]
					s.add(i)
					s.add(j)
					break
		return sum


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		i = N - 1
		sum = 0
		while i > 0:
			if arr[i] - arr[i - 1] < K:
				sum += arr[i] + arr[i - 1]
				i -= 1
			i -= 1
		return sum


import math

class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort(reverse=True)
		sumres = 0
		(i, j) = (0, 1)
		while i < N and j < N:
			if arr[i] - arr[j] < K:
				sumres += arr[i] + arr[j]
				i = j + 1
				j = i + 1
			else:
				i = i + 1
				j = i + 1
		return sumres


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		res = []
		(a, b) = (N - 1, N - 2)
		while a >= 0 and b >= 0:
			if arr[a] - arr[b] < K:
				res.append(arr[a])
				res.append(arr[b])
				a -= 2
				b -= 2
			else:
				a -= 1
				b -= 1
		return sum(res)


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		s = 0
		i = len(arr) - 2
		n1 = arr[-1]
		l = []
		while i >= 0:
			if n1 - arr[i] < K:
				l.append([n1, arr[i]])
				s += n1 + arr[i]
				i -= 1
				n1 = arr[i]
				i -= 1
			else:
				n1 = arr[i]
				i -= 1
		return s


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		su = 0
		i = N - 1
		while i > 0:
			if abs(arr[i] - arr[i - 1]) < K:
				su += arr[i] + arr[i - 1]
				i -= 1
			i -= 1
		return su


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort()
		maxSum = 0
		i = n - 1
		while i > 0:
			if arr[i] - arr[i - 1] < k:
				maxSum += arr[i] + arr[i - 1]
				i -= 1
			i -= 1
		return maxSum


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort()
		dp = [0] * n
		dp[0] = 0
		for i in range(1, n):
			dp[i] = dp[i - 1]
			if arr[i] - arr[i - 1] < k:
				if i >= 2:
					dp[i] = max(dp[i], dp[i - 2] + arr[i] + arr[i - 1])
				else:
					dp[i] = max(dp[i], arr[i] + arr[i - 1])
		return dp[n - 1]


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, k):
		i = 0
		ans = 0
		arr = sorted(arr, reverse=True)
		while i < len(arr):
			if i + 1 < len(arr) and abs(arr[i] - arr[i + 1]) < k:
				ans += arr[i + 1] + arr[i]
				i += 2
				continue
			i += 1
		return ans


from itertools import combinations

class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		arr = arr[::-1]
		ans = 0
		i = 0
		while i < N - 1:
			if arr[i] - arr[i + 1] < K:
				ans += arr[i] + arr[i + 1]
				i += 2
			else:
				i += 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		sol = 0
		i = 0
		j = 1
		arr.sort(reverse=True)
		while i < N - 1 and j < N:
			if arr[i] - arr[j] < K:
				sol += arr[i] + arr[j]
				i = j + 1
				j = i + 1
			else:
				i += 1
				j += 1
		return sol


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, a, n, k):
		a.sort()
		ans = 0
		lastTaken = False
		for i in range(n - 2, -1, -1):
			if lastTaken:
				lastTaken = False
			elif a[i + 1] - a[i] < k:
				ans += a[i + 1] + a[i]
				lastTaken = True
			else:
				lastTaken = False
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort()
		ans = 0
		arr = arr[::-1]
		i = 0
		while i < n - 1:
			if arr[i] - arr[i + 1] < k:
				ans += arr[i] + arr[i + 1]
				i += 2
			else:
				i += 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort(reverse=True)
		summ = 0
		i = 0
		while i < N - 1:
			x = abs(arr[i] - arr[i + 1])
			if x < K:
				summ += arr[i]
				summ += arr[i + 1]
				i += 2
			else:
				i += 1
		return summ


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		a = []
		k = 0
		for hm in range(len(arr) - 1):
			a.append(arr[hm + 1] - arr[hm])
		g = len(a) - 1
		while g >= 0:
			if a[g] < K:
				k += arr[g]
				k += arr[g + 1]
				g -= 2
			else:
				g -= 1
		return k


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort(reverse=True)
		l = []
		i = 0
		s = 0
		while i < n - 1:
			if arr[i] - arr[i + 1] < k:
				l.append((arr[i], arr[i + 1]))
				i += 2
			else:
				i += 1
		for i in l:
			s += sum(i)
		return s


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort(reverse=True)
		h = {}
		for i in arr:
			if i in h:
				h[i] += 1
			else:
				h[i] = 1
		i = 0
		j = 1
		s = 0
		while i < n - 1 and j < n:
			if i == j:
				j += 1
				continue
			if arr[i] in h or arr[j] in h:
				if arr[i] in h:
					if h[arr[i]] == 0:
						i += 1
						continue
				if arr[j] in h:
					if h[arr[j]] == 0:
						j += 1
						continue
			d = arr[i] - arr[j]
			if d < k:
				s += arr[i]
				s += arr[j]
				h[arr[i]] -= 1
				h[arr[j]] -= 1
				i = j + 1
				j = i + 1
			else:
				i = j
				j += 1
		return s


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, k):
		arr.sort(reverse=True)
		f = 0
		s = 0
		for i in range(0, N - 1):
			if f == 1:
				f = 0
				continue
			if arr[i] - arr[i + 1] < k:
				s += arr[i] + arr[i + 1]
				f = 1
		return s


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort(reverse=True)
		flg = 0
		sum1 = 0
		for i in range(0, N - 1):
			if flg == 1:
				flg = 0
				continue
			if arr[i] - arr[i + 1] < K:
				sum1 += arr[i] + arr[i + 1]
				flg = 1
		return sum1


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, k):
		arr.sort()
		summ = 0
		i = N - 1
		while i > 0:
			if arr[i] - arr[i - 1] < k:
				summ += arr[i] + arr[i - 1]
				i = i - 2
			else:
				i -= 1
		return summ


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr = sorted(arr, reverse=True)
		ans = 0
		i = 0
		while i < N:
			if i + 1 < N and arr[i] - arr[i + 1] < K:
				ans += arr[i]
				ans += arr[i + 1]
				i += 2
			else:
				i += 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		arr.reverse()
		valid = [False for i in range(N)]
		res = 0
		for i in range(N):
			if valid[i]:
				continue
			for j in range(i + 1, N):
				if valid[j] is False and abs(arr[i] - arr[j]) < K:
					valid[j] = True
					valid[i] = True
					res += arr[i] + arr[j]
					break
		return res


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, a, n, k):
		a.sort(reverse=True)
		i = 0
		sum = 0
		while i < n - 1:
			if a[i] - a[i + 1] < k:
				sum += a[i] + a[i + 1]
				i += 2
			else:
				i += 1
		return sum


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, a, n, k):
		a.sort(reverse=True)
		i = 0
		sum = 0
		b = []
		while len(a) > 1:
			if a[0] - a[1] < k:
				b.append((a[0], a[1]))
				a.pop(0)
				a.pop(0)
			else:
				a.pop(0)
		for i in range(len(b)):
			sum += b[i][0] + b[i][1]
		return sum


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, a, N, k):
		a.sort()
		i = N - 1
		Sum = 0
		while i > 0:
			if a[i] - a[i - 1] < k:
				Sum += a[i] + a[i - 1]
				i -= 2
			else:
				i -= 1
		return Sum


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		ans = 0
		s = set()
		i = N - 1
		while i > 0:
			if arr[i] - arr[i - 1] < K:
				ans += arr[i - 1] + arr[i]
				i = i - 1
			i = i - 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, k):
		arr.sort()
		j = N - 1
		sum1 = 0
		while j >= 1:
			if arr[j] - arr[j - 1] < k:
				sum1 = sum1 + arr[j] + arr[j - 1]
				j = j - 2
			else:
				j = j - 1
		return sum1


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort(reverse=True)
		n = len(arr)
		(i, j) = (0, n - 1)
		res = 0
		while i < j:
			if abs(arr[i] - arr[i + 1]) < K:
				res += arr[i + 1] + arr[i]
				i += 2
			else:
				i += 1
		return res


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		summa = 0
		while len(arr) > 1:
			if arr[-1] - arr[-2] >= K:
				arr.pop()
			else:
				summa += arr.pop() + arr.pop()
		return summa


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		total = []
		arr.sort()
		prev = arr[n - 1]
		i = n - 2
		while i > -1:
			if prev - arr[i] < k:
				total.append(prev)
				total.append(arr[i])
				if i - 1 > 0:
					prev = arr[i - 1]
					i = i - 2
				else:
					break
			else:
				prev = arr[i]
				i -= 1
		return sum(total)


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		ans = []
		i = N - 1
		while i > 0:
			if arr[i] - arr[i - 1] < K:
				ans.append([arr[i - 1], arr[i]])
				i -= 2
			else:
				i -= 1
		summ = 0
		for i in range(len(ans)):
			summ += ans[i][0] + ans[i][1]
		return summ


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, a, N, K):
		a.sort()
		i = N - 1
		result = 0
		while i > 0:
			if a[i] - a[i - 1] < K:
				result += a[i] + a[i - 1]
				i -= 2
			else:
				i -= 1
		return result


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		arr.sort()
		arr.reverse()
		lst = []
		i = 0
		while i < len(arr) - 1:
			if arr[i] - arr[i + 1] < K:
				lst.append(arr[i])
				lst.append(arr[i + 1])
				i = i + 1
			i = i + 1
		x = sum(lst)
		return x


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, n, k):
		arr.sort(reverse=True)
		i = 0
		j = 1
		ans = 0
		while i < n - 1 and j < n:
			if arr[i] - arr[j] < k:
				ans += arr[i] + arr[j]
				i = j + 1
				j = i + 1
			else:
				i += 1
				j += 1
		return ans


class Solution:

	def maxSumPairWithDifferenceLessThanK(self, arr, N, K):
		s = 0
		arr.sort()
		i = N - 1
		j = N - 2
		while i > 0 and j > -1:
			if arr[i] - arr[j] < K:
				s += arr[i]
				s += arr[j]
				i -= 2
				j -= 2
			else:
				i -= 1
				j -= 1
		return s