O(n) Solution ... utilizing the mathematical concept a+b = n, where if a is present in our array then we need to determine if b = n - a is also present or not.
def hasPairsWithSum(array,sum):
d = {}
for i in range(len(array)):
if(array[i] in d):
d[array[i]].append(i)
else:
d[array[i]] = [i]
ans = []
for i in range(len(array)):
val = sum - array[i]
if(val in d):
if(d[val][0] == i):
if(len(d[val]) > 1):
ans.append((i,d[val][1]))
break
else:
continue
else:
ans.append((i,d[val][0]))
break
return ans
print(hasPairsWithSum([4, 4, 4, 4], 8))
O(nlogn) solution ... by storing indexes with elements and sorting them by their values, followed by running a loop using the Two Pointers concept.
def hasPairsWithSum(array,sum):
arr = []
for i in range(len(array)):
arr.append((array[i],i))
arr.sort()
i = 0
j = len(array)-1
ans = []
while(i<j):
tmp_sum = arr[i][0] + arr[j][0]
if(tmp_sum == sum):
ans.append((arr[i][1] , arr[j][1]))
#add your logic if you want to find all possible indexes instead of break
break
elif(tmp_sum < sum):
i = i + 1
elif(tmp_sum > sum):
j = j - 1
return ans
print(hasPairsWithSum([1,2,4,4],8))
- Note: If you aim to find all possible solutions, these approaches may not suffice. You can either add your own logic in the while loop or consider using binary search with traversal on every element and storing the indexes in a set (which could lead to worst-case scenario of O(n^2) as all possible values need to be found). For example, with input [4,4,4,4,4,4] and sum = 8, trying to print all possible indexes will require running it up to n^2 (why? Reason being total possible solutions are 5+4+3+2+1 = n*(n-1)/2 ≈ n^2).