Given an array A[ ] of N of  integers, find the distinct index of values that satisfy A + B = C + D where A,B,C & D are integers values in the array.
Note: As there may be multiple pairs satisfying the equation return lexicographically smallest order of  A, B, C and D and return all as -1 if there are no pairs satisfying the equation.
 
Example 1:
Input:
N = 7
A[] = {3, 4, 7, 1, 2, 9, 8}
Output:
0 2 3 5
Explanation:
A[0] + A[2] = 3+7 = 10
A[3] + A[5] = 1+9 = 10
Example 2:
Input:
N = 4
A[] = {424, 12, 31, 7}
Output:
-1 -1 -1 -1
Explanation:
There are no pairs satisfying the equation.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function satisfyEqn() which takes an Integer N and an array A[] of size N as input and returns a vector of 4 integers denoting A, B, C, and D respectively.
 
Expected Time Complexity: O(N^{2}*logN^{2})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
1 <= N <= 500
1 <= A[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def satisfyEqn(self, A, N):

        # code here 

Solutions:
class Solution:

	def satisfyEqn(self, a, n):
		d = dict()
		s = list()
		sum = 0
		for i in range(n):
			for j in range(i + 1, n):
				sum = a[i] + a[j]
				if sum not in d:
					d[sum] = [i, j]
				elif i != d[sum][0] and j != d[sum][0] and (i != d[sum][1]) and (j != d[sum][1]):
					s.append([d[sum][0], d[sum][1], i, j])
		if len(s) == 0:
			return [-1, -1, -1, -1]
		return min(s)


class Solution:

	def solve(self, A, summ, a, b):
		for x in range(len(A)):
			if A[x] != None:
				cval = A[x]
				A[x] = None
				if summ - cval in A:
					for y in range(len(A)):
						if A[y] == summ - cval:
							return [a, b, x, y]
				A[x] = cval
		return []

	def satisfyEqn(self, A, N):
		ans = []
		for a in range(0, N - 1):
			for b in range(a + 1, N):
				summ = A[a] + A[b]
				aval = A[a]
				bval = A[b]
				A[a] = None
				A[b] = None
				ans1 = ob.solve(A, summ, a, b)
				if len(ans1) != 0:
					return ans1
				A[a] = aval
				A[b] = bval
		return [-1, -1, -1, -1]


from collections import defaultdict

class Solution:

	def satisfyEqn(self, A, N):
		map = defaultdict(list)
		ans = 0
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				s = A[i] + A[j]
				if s in map:
					if map[s][0] != i and map[s][1] != j and (map[s][0] != j) and (map[s][1] != i):
						temp = map[s][:2] + [i, j]
						if not ans or ans > temp:
							while map[s]:
								map[s].pop()
							map[s].extend(temp)
							ans = map[s]
				else:
					map[s].extend([i, j])
		return [-1, -1, -1, -1] if not ans else ans


class Solution:

	def satisfyEqn(self, arr, n):
		map = {}
		mi = [100000000.0, 100000000.0, 100000000.0, 100000000.0]
		for i in range(n):
			for j in range(i + 1, n):
				sum = arr[i] + arr[j]
				if sum in map and i not in map[sum] and (j not in map[sum]):
					lis = map[sum].copy()
					lis.extend([i, j])
					mi = min(mi, lis)
				elif sum not in map:
					map[sum] = [i, j]
				else:
					map[sum] = min(map[sum], [i, j])
		if mi != [100000000.0, 100000000.0, 100000000.0, 100000000.0]:
			return mi
		return [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		for i in range(0, N):
			for j in range(0, N):
				for k in range(0, N):
					for l in range(0, N):
						if A[i] + A[j] == A[k] + A[l] and i != j and (k != l) and (j != k) and (i != k) and (j != l) and (i != l):
							return (i, j, k, l)
		return (-1, -1, -1, -1)


class Solution:

	def satisfyEqn(self, A, N):
		d = {}
		c = 0
		l = []
		for i in range(N - 1):
			for j in range(i + 1, N):
				s = A[i] + A[j]
				if s not in d:
					d[s] = [i, j]
				elif i not in d[s] and j not in d[s]:
					d[s] += [i, j]
					if c == 0:
						l = d[s]
						c = 5
					elif d[s] < l:
						l = d[s]
		if len(l) >= 4:
			return l[0:4]
		else:
			return [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		d = {}
		result = [float('inf'), float('inf'), float('inf'), float('inf')]
		is_result = False
		for i in range(N - 1):
			for j in range(i + 1, N):
				summa = A[i] + A[j]
				if summa not in d:
					d[summa] = [i, j]
				elif len(set(d[summa] + [i, j])) == 4:
					result = min(result, d[summa] + [i, j])
					is_result = True
		return result if is_result else [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		mp = {}
		ans = [999, 999, 999, 999]
		temp = [None]
		for i in range(N):
			for j in range(i + 1, N):
				if A[i] + A[j] not in mp:
					mp[A[i] + A[j]] = (i, j)
				else:
					temp[0] = mp[A[i] + A[j]]
					(a, b, c, d) = (temp[0][0], temp[0][1], i, j)
					if a == c or a == d or b == c or (b == d):
						continue
					elif a < ans[0]:
						(ans[0], ans[1], ans[2], ans[3]) = (a, b, c, d)
					elif a == ans[0]:
						if b < ans[1]:
							(ans[0], ans[1], ans[2], ans[3]) = (a, b, c, d)
						elif b == ans[1]:
							if c < ans[2]:
								(ans[0], ans[1], ans[2], ans[3]) = (a, b, c, d)
							elif c == ans[2]:
								if d < ans[3]:
									(ans[0], ans[1], ans[2], ans[3]) = (a, b, c, d)
								else:
									continue
		if ans == [999, 999, 999, 999]:
			ans = [-1, -1, -1, -1]
		return ans


class Solution:

	def satisfyEqn(self, A, N):
		dic = {}
		ans = [N, N, N, N]
		for i in range(N):
			for j in range(i + 1, N):
				cur_sum = A[i] + A[j]
				if dic.get(cur_sum, -1) == -1:
					dic[cur_sum] = (i, j)
				else:
					(x, y) = dic[cur_sum]
					if x != i and x != j and (y != i) and (y != j):
						cur_ans = [x, y, i, j]
						if cur_ans < ans:
							ans = cur_ans
		if ans == [N, N, N, N]:
			return [-1, -1, -1, -1]
		return ans


import heapq

class Solution:

	def satisfyEqn(self, A, N):
		temp = {}
		solution = []
		for i in range(N - 1):
			for j in range(i + 1, N):
				sum_t = A[i] + A[j]
				if sum_t not in temp:
					temp[sum_t] = [i, j]
				elif len(set(temp[sum_t] + [i, j])) == 4:
					heapq.heappush(solution, temp[sum_t] + [i, j])
		if solution == []:
			return [-1, -1, -1, -1]
		else:
			return solution[0]


class Solution:

	def satisfyEqn(self, A, N):
		dic = dict()
		s = list()
		for i in range(N):
			for j in range(i + 1, N):
				sum = A[i] + A[j]
				if sum not in dic:
					dic[sum] = [i, j]
				elif i != dic[sum][0] and i != dic[sum][1] and (j != dic[sum][0]) and (j != dic[sum][1]):
					s.append([dic[sum][0], dic[sum][1], i, j])
		if len(s) == 0:
			return [-1, -1, -1, -1]
		return min(s)


class Solution:

	def satisfyEqn(self, A, N):
		dic = {}
		res = []
		n = 0
		for i in range(N):
			for j in range(i + 1, N):
				sval = A[i] + A[j]
				if sval not in dic:
					dic[sval] = [i, j]
				elif dic[sval][0] != i and dic[sval][0] != j and (dic[sval][1] != i) and (dic[sval][1] != j):
					res.append([dic[sval][0], dic[sval][1], i, j])
					n += 1
		if n > 0:
			return min(res)
		return [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		Hash = {}
		Ans = []
		flag = 0
		for i in range(N):
			for j in range(i + 1, N):
				sum = A[i] + A[j]
				if sum not in Hash:
					Hash[sum] = (i, j)
				else:
					pp = Hash[sum]
					if pp[0] != i and pp[0] != j and (pp[1] != i) and (pp[1] != j):
						ans = []
						ans.append(pp[0])
						ans.append(pp[1])
						ans.append(i)
						ans.append(j)
						if not Ans:
							Ans = ans[:]
						else:
							shouldReplace = False
							for i1 in range(len(Ans)):
								if Ans[i1] < ans[i1]:
									break
								if Ans[i1] > ans[i1]:
									shouldReplace = True
									break
							if shouldReplace:
								Ans = ans
		if not Ans:
			return [-1, -1, -1, -1]
		return Ans


class Solution:

	def satisfyEqn(self, A, N):
		uniqueSubset = {}
		ans = (N + 1, N + 1, N + 1, N + 1)
		for i in range(N):
			for j in range(i + 1, N):
				tot = A[i] + A[j]
				if tot in uniqueSubset:
					if i not in uniqueSubset[tot] and j not in uniqueSubset[tot]:
						temp = (*uniqueSubset[tot], i, j)
						ans = min(ans, temp)
				else:
					uniqueSubset[tot] = (i, j)
		if ans == (N + 1, N + 1, N + 1, N + 1):
			return (-1, -1, -1, -1)
		return ans


class Solution:

	def satisfyEqn(self, A, N):
		m = {}
		ans = [float('inf') for i in range(4)]
		curr = [0 for i in range(4)]
		for i in range(N):
			for j in range(i + 1, N):
				s = A[i] + A[j]
				if s not in m:
					m[s] = [i, j]
				p = m[s]
				if i != p[0] and i != p[1] and (j != p[0]) and (j != p[1]):
					curr[0] = p[0]
					curr[1] = p[1]
					curr[2] = i
					curr[3] = j
					replace = False
					for k in range(4):
						if curr[k] < ans[k]:
							replace = True
							break
						elif curr[k] > ans[k]:
							break
					if replace:
						ans[0] = curr[0]
						ans[1] = curr[1]
						ans[2] = curr[2]
						ans[3] = curr[3]
		if ans[0] == float('inf'):
			return [-1, -1, -1, -1]
		return ans


class Solution:

	def satisfyEqn(self, a, n):
		d = {}
		l1 = []
		c = 9
		for i in range(0, n - 1):
			for j in range(i + 1, n):
				k = a[i] + a[j]
				if k not in d:
					d[k] = [i, j]
				elif i not in d[k] and j not in d[k]:
					d[k] += [i, j]
					if c == 9:
						l1 = d[k]
						c = 0
					elif d[k] < l1:
						l1 = d[k]
		if len(l1) < 4:
			return [-1, -1, -1, -1]
		else:
			return l1[0:4]


class Solution:

	def satisfyEqn(self, A, N):
		res = (float('inf'), float('inf'), float('inf'), float('inf'))
		h = {}
		for i in range(N):
			for j in range(i + 1, N):
				if A[i] + A[j] not in h:
					h[A[i] + A[j]] = (i, j)
				else:
					(a, b) = h[A[i] + A[j]]
					if a == i or b == i or a == j or (b == j):
						continue
					else:
						res = min(res, (a, b, i, j))
		return list(res) if res != (float('inf'), float('inf'), float('inf'), float('inf')) else [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		for i in range(N):
			for j in range(N):
				if i == j:
					continue
				for k in range(N):
					if k == i or k == j:
						continue
					for l in range(N):
						if l == i or l == j or l == k:
							continue
						if A[i] + A[j] == A[k] + A[l]:
							return [i, j, k, l]
		return [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		dict1 = {}
		for i in range(N - 1):
			for j in range(i + 1, N):
				sum1 = A[i] + A[j]
				if sum1 not in dict1:
					dict1[sum1] = [i, j]
				else:
					x = dict1[sum1]
					if len(x) < 4 and i not in x and (j not in x):
						dict1[sum1].extend([i, j])
		dict2 = {}
		for i in dict1.items():
			if len(i[1]) == 4:
				dict2[i[0]] = i[1]
		s = sorted(dict2.items(), key=lambda x: x[1])
		if len(s) != 0:
			return s[0][1]
		else:
			return [-1, -1, -1, -1]


class Solution:

	def satisfyEqn(self, A, N):
		p = {}
		ans = []
		for i in range(N):
			for j in range(i + 1, N):
				x = A[i] + A[j]
				if x in p:
					m = p[x]
					a = [m[0], m[1], i, j]
					if m[0] != i and m[1] != i and (m[0] != j) and (m[1] != j):
						ans.append(a)
				else:
					p[x] = [i, j]
		if len(ans) == 0:
			ans.append([-1, -1, -1, -1])
		return min(ans)


import math

class Solution:

	def satisfyEqn(self, A, N):
		found = False
		hash = {}
		ans = [math.inf, math.inf, math.inf, math.inf]
		for i in range(N):
			for j in range(i + 1, N):
				prev = hash.get(A[i] + A[j])
				if prev:
					if i not in prev and j not in prev:
						ans = min(prev + [i, j], ans)
						found = True
						hash[A[i] + A[j]] = min([i, j], prev)
				else:
					hash[A[i] + A[j]] = [i, j]
		return ans if found else (-1, -1, -1, -1)


class Solution:

	def satisfyEqn(self, A, N):
		mp = dict()
		res = comp = [float('inf')] * 4
		for i in range(N):
			for j in range(i + 1, N):
				sm = A[i] + A[j]
				if sm in mp:
					(a, b) = mp[sm]
					f = 1
					if a == i or b == i or b == j:
						f = 0
					temp = [a, b, i, j]
					if f:
						res = min(res, temp)
				else:
					mp[sm] = (i, j)
		return res if res != comp else [-1] * 4


class Solution:

	def satisfyEqn(self, A, N):
		r = N * N + 3
		dict = {}
		no = 0
		ans = [-1] * 4
		for i in range(N):
			for j in range(i + 1, N):
				s = A[i] + A[j]
				no += 1
				if s in dict:
					aa = dict[s]
					if aa[0] < r and i != aa[1] and (i != aa[2]) and (j != aa[1]) and (j != aa[2]):
						r = aa[0]
						ans = [aa[1], aa[2], i, j]
				else:
					dict[s] = [no, i, j]
		return ans


class Solution:

	def satisfyEqn(self, a, N):
		hsh = {}
		ans = [500]
		for i in range(N):
			for j in range(i + 1, N):
				sm = a[i] + a[j]
				if sm in hsh:
					if i not in hsh[sm]:
						temp = list(hsh[sm] + [i, j])
						ans = min(ans, temp)
				else:
					hsh[sm] = [i, j]
		if ans[0] != 500:
			return ans
		else:
			return [-1] * 4


class Solution:

	def satisfyEqn(self, arr, n):
		d = {}
		res = []
		for i in range(n):
			for j in range(i + 1, n):
				s = arr[i] + arr[j]
				if s not in d:
					d[s] = [i, j]
				else:
					(a, b) = d[s]
					if a != i and a != j and (b != i) and (b != j):
						ans = []
						ans.extend([a, b, i, j])
						if not res:
							res = ans
						else:
							res = min(res, ans)
		if not res:
			return [-1, -1, -1, -1]
		return res


class Solution:

	def satisfyEqn(self, A, N):
		d = {}
		s = [N] * 4
		for i in range(N):
			for j in range(i + 1, N):
				z = A[i] + A[j]
				if z in d:
					if i == d[z][1] or i == d[z][0] or j == d[z][0] or (j == d[z][1]):
						continue
					k = [d[z][0], d[z][1], i, j]
					if k < s:
						s = k
				else:
					d[z] = [i, j]
		if s == [N] * 4:
			return [-1, -1, -1, -1]
		else:
			return s


class Solution:

	def satisfyEqn(self, A, N):
		d = {}
		res = []
		for (i, num) in enumerate(A):
			for j in range(i + 1, N):
				sumVal = A[i] + A[j]
				if sumVal not in d:
					d[sumVal] = (i, j)
				elif i not in d[sumVal] and j not in d[sumVal]:
					if len(res) == 0:
						res.append([d[sumVal][0], d[sumVal][1], i, j])
					elif res[0] > [d[sumVal][0], d[sumVal][1], i, j]:
						res[0] = [d[sumVal][0], d[sumVal][1], i, j]
		if len(res) == 0:
			return [-1] * 4
		else:
			return res[0]


class Solution:

	def satisfyEqn(self, A, N):
		ans = [-1, -1, -1, -1]
		mapu = {}
		for i in range(N):
			for j in range(i + 1, N):
				sumi = A[i] + A[j]
				if sumi not in mapu:
					mapu[sumi] = [i, j]
				elif i not in mapu[sumi] and j not in mapu[sumi]:
					tans = [mapu[sumi][0], mapu[sumi][1], i, j]
					if ans[0] == -1:
						ans = tans
					elif tans < ans:
						ans = tans
		return ans


class Solution:

	def satisfyEqn(self, arr, n):

		def lex(a, b):
			for i in range(n):
				if a[i] > b[i]:
					return b
				elif a[i] < b[i]:
					return a
			return a
		map = {}
		ans = [float('inf'), float('inf'), float('inf'), float('inf')]
		for i in range(n):
			for j in range(i + 1, n):
				sum = arr[i] + arr[j]
				if sum in map:
					if map[sum][0] != i and map[sum][0] != j and (map[sum][1] != i) and (map[sum][1] != j):
						temp = [map[sum][0], map[sum][1], i, j]
						ans = lex(ans, temp)
				else:
					map[sum] = [i, j]
		if ans[0] == float('inf'):
			return [-1, -1, -1, -1]
		return ans


class Solution:

	def satisfyEqn(self, A, N):
		dic = {}
		ans = [N] * 4
		for i in range(N - 1):
			for j in range(i + 1, N):
				sum1 = A[i] + A[j]
				if sum1 not in dic:
					dic[sum1] = [i, j]
				elif dic[sum1] and i not in dic[sum1] and (j not in dic[sum1]):
					ans = min(ans, dic[sum1] + [i, j])
					dic[sum1] = []
		if ans == [N] * 4:
			return [-1, -1, -1, -1]
		return ans


class Solution:

	def satisfyEqn(self, A, N):
		ans = []
		hash = {}
		for i in range(N):
			for j in range(i + 1, N):
				required_sum = A[i] + A[j]
				if required_sum not in hash:
					hash[required_sum] = (i, j)
				elif hash[required_sum][0] != i and hash[required_sum][0] != j and (hash[required_sum][1] != i) and (hash[required_sum][1] != j):
					(a, b, c, d) = (hash[required_sum][0], hash[required_sum][1], i, j)
					if not ans or [a, b, c, d] < ans:
						ans = [a, b, c, d]
		if len(ans) == 0:
			return [-1, -1, -1, -1]
		return ans


class Solution:

	def satisfyEqn(self, A, N):
		d = dict()
		store = [10 ** 6, 10 ** 6, 10 ** 6, 10 ** 6]
		for i in range(N):
			for j in range(i + 1, N):
				if A[i] + A[j] in d:
					first = d[A[i] + A[j]][0]
					second = d[A[i] + A[j]][1]
					if not len(set([first, second]) & set([i, j])) == 0:
						continue
					if store > [first, second, i, j]:
						store = [first, second, i, j]
				else:
					d[A[i] + A[j]] = [i, j]
		if store[0] == 10 ** 6:
			return [-1, -1, -1, -1]
		return store


class Solution:

	def satisfyEqn(self, A, N):
		flag = False
		Dict = {}
		Valid = {}
		for i in range(N):
			for j in range(i + 1, N):
				S = A[i] + A[j]
				if S in Dict:
					if len(Dict[S]) == 2:
						if i != Dict[S][0] and i != Dict[S][1]:
							Dict[S] += [i, j]
							Valid[S] = Dict[S]
							flag = True
				else:
					Dict[S] = [i, j]
		ans = [501] * 4
		for (k, v) in Valid.items():
			if v < ans:
				ans = v
		if flag:
			return ans
		else:
			return [-1] * 4


class Solution:

	def satisfyEqn(self, A, N):
		arr = [-1, -1, -1, -1]
		for i in range(N):
			for j in range(i + 1, N):
				for k in range(N):
					for l in range(k + 1, N):
						if not (i < j and i < k and (k < l) and (j != k) and (j != l)):
							continue
						if A[i] + A[j] == A[k] + A[l]:
							(arr[0], arr[1], arr[2], arr[3]) = (i, j, k, l)
							return arr
		return arr


class Solution:

	def satisfyEqn(self, A, N):
		dp = {}
		ans = [10 ** 6, 10 ** 6, 10 ** 6, 10 ** 6]
		for i in range(N):
			for j in range(i + 1, N):
				sumval = A[i] + A[j]
				if sumval not in dp:
					dp[sumval] = (i, j)
					continue
				pair = dp.get(sumval)
				if pair[0] != i and pair[1] != j and (pair[0] != j) and (pair[1] != i):
					curr = [0] * 4
					curr[0] = pair[0]
					curr[1] = pair[1]
					curr[2] = i
					curr[3] = j
					if ans[0] == 10 ** 6:
						for k in range(4):
							ans[k] = curr[k]
					else:
						replace = False
						for k in range(4):
							if ans[k] > curr[k]:
								replace = True
								break
							elif curr[k] > ans[k]:
								break
						if replace:
							for k in range(4):
								ans[k] = curr[k]
		if ans[0] == 10 ** 6:
			for k in range(4):
				ans[k] = -1
		return ans


class Solution:

	def satisfyEqn(self, A, N):
		flag = False
		a = b = -1
		for i in range(N):
			for j in range(i + 1, N):
				tar = A[i] + A[j]
				ind = set()
				ind.add(i)
				ind.add(j)
				vis = {}
				d = c = float('inf')
				for k in range(N):
					if k in ind:
						continue
					if tar - A[k] in vis and vis[tar - A[k]] not in ind:
						if c > vis[tar - A[k]] or (c == vis[tar - A[k]] and d > k):
							a = i
							b = j
							c = vis[tar - A[k]]
							d = k
							flag = True
					if A[k] not in vis:
						vis[A[k]] = k
				if flag:
					break
			if flag:
				break
		if flag:
			return [a, b, c, d]
		return [-1, -1, -1, -1]