## Google Interview Question

Backend Developers**Team:**Load Balancer

**Country:**United States

```
# This solution supports negative integers and elements duplication (e.g. [3, 5, 2, -4, 8, -4, 11, 11]).
# With `n` = number of elements in arr and `m` = number of indices of a certain complement
# Time complexity = O(n * m)
# Space complexity = O(n * m)
def twoSum(arr, sum):
compl = {}
result = []
for i in range(len(arr)): # O(n)
n = arr[i]
if sum-n in compl:
for j in compl[sum-n]: # O(m)
result.append([arr[j], n])
if n in compl:
compl[n].append(i)
else:
compl[n] = [i]
return result
```

Optimized solution using Bucket sort based approach. The integer includes negative integer as well.

- anshuman101 February 22, 2020For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.

My approach

/**

* Approach 1: Print all the subset and find the matching sum

* Approach 2: Apply subset sum problem which 0(cnt * a.length)

* Approach 3: 0(n) how is it possible. Bucket sort based logic

*/

Approach 3 implementation is here

public class TwoSumProblem {

private static void findTwoSum(int[] a, int cnt)

{

int[] b = new int[100];

for(int i = 0 ; i < a.length ; i++)

{

b[a[i] + 50] = b[a[i] + 50] + 1;

}

int t1 = 0;

for(int i = 0 ; i < a.length ; i++)

{

if(b[a[i] + 50] == 1 && b[cnt - a[i] + 50] == 1 && cnt - a[i] + 50 != a[i] + 50)

{

b[a[i] + 50] = b[a[i] + 50] - 1;

b[cnt - a[i] + 50] = b[cnt - a[i] + 50] - 1;

t1 = cnt - a[i];

System.out.println("Pair is " + a[i] + " and " + t1);

}

}

}

public static void main(String[] args) {

int[] a = {3, 5, 2, -4, 8, 11} ;

findTwoSum(a, 7);

}

}