Better Search Strategy for Linear Complexity

Search is always an interesting question to solve depending upon the constraints of the problem.

Let's take up the following problem for discussion: You need to find within a given number of integers whether the sum of 2 integers is equal to a given sum.

A naive solution to this problem would be 

for (int i= 0; i less than n; i++ )
          for (int j=0; j  less than n; j++)         
               if(arr[i]]+arr[j] == sum)
             return true;
      }
}

The above solution would be of complexity O(n^2). Suppose if you have a large set of numbers the overhead would be huge;

The second alternative could be to sort the numbers and then have 2 pointers one moving from '0' other from 'n-1' both approaching each other with a logic that n-1 would move till the rightmost number is less than the sum while the leftmost would move from 0 towards the right so that

a[leftmost]+a[rightmost] == sum;

This strategy would have issues where you need to sort the numbers first which has its own complexity and the total complexity would be

sortComplexity + n log(n) .. where the binary search would cut the number by half each time which is logarithmic in nature.

If we were looking for a linear solution, we can have another alternative like,

1. Take converse of each number (sum - current) 
2. Store in a set (Hash Set in some cases) // which holds unique values
3. Check if the coming numbers exist in the set already. 
4. if the number exists return true else false.

This strategy would have a linear complexity since the search is linear and the lookup in a set as well is constant.

The implementation for this idea in python is below.

def search(givenList, s):
    complements = set()
    for i in range(len(givenList)):
         if givenList[i] in complements:
             return True
         complements.add(s - givenList[i])
     
    return False 


if __name__ == '__main__':
    given = [10, 7, 8, 24, 46, 3 , 86, 35]
    result = search(given,93)
    print(result)
    pass