Find pairs in array whose sums already exist in array in Python

In this article, we are basically going to solve an easy problem using two different data structures.
The problem statement being we have to find all the pair of integer elements from an array(list) such that sum itself is an element of the array.

Input: a=[1,2,3,4,5,6]

Output: 1 2
        1 3
        1 4
        1 5
        2 3
        2 4

The most basic approach would include three-loop. Resulting in time complexity of O(n^3).

def suminarray(a):
    k=0
    lis=[]
    n=len(a)
    
   
    for i in range(n-1):
        for j in range(i+1,n):
            for l in range(n):
                if(a[i]+a[j]==a[l]):
                    lis.append(a[i],a[j])
                    k+=1

    
    if(k>0): 
      return lis 
    else: 
      return ("NOT EXIST")

Instead of a third loop, we can go for a data structure to store the array values to easily retrieve them while searching it.
We will first use a list(original array itself)

def suminarray(a):
    k=0
    lis=[]
    n=len(a)
    for i in range(n-1):
        for j in range(i+1,n):
            if (a[i]+a[j]) in a:
                lis.append([a[i],a[j]])
                k+=1

    if(k>0):
        return lis
    else:
        return ("NOT EXIST")

We will now use the dictionary which is said most efficient data structure when it comes to searching an element.

def suminarray(a):
    k=0
    lis=[]
    n=len(a)
    s={i : 1 for i in a}
    print(s)
    for i in range(n-1):
        for j in range(i+1,n):
            if s.get((a[i]+a[j]),0)==1:
                lis.append([a[i],a[j]])
                k+=1

    if(k>0):
        return lis
    else:
        return ("NOT EXIST")

 

That’s it for the article, please do comment if you could come up with more efficient code or data structures.

Leave a Reply

Your email address will not be published.