## Wednesday, August 12, 2020

### [Interview Question ][Data Structure] Two Sum Problem -Array

Two sum problem is one of the most asked data structure questions for a java developer interview. There could be one or more ways to solve the problem but i am trying to give the optimized solution to this problem.

Lets first see the Problem Statement.

Problem Statement - Given an array, We need to find all the possible sets of 2 elements whose sum is equal to the target sum.

Solution: Given an array, lets say [10,-2,5,3,1,7,4] and given a target = 8 , We need to find all the possible 2 elements whose sum is equal to the 8.

the possible output will be

[10,-2] ,[5,3],[1,7]

Pseudo code-

• Lets first sort the array.
• After sorting, take 2 pointers, one is leftmost & second is rightmost.
• we will start taking each element from left & right then check some of both the element.
• If the sum is less then the target sum, then move the left pointer by one.
• if the sum is greater than the target sum, then move the right pointer to left by one.
• else if it is equal to target then put the elements one result array and move both left & right pointer by one.
Now let see the Java implementations.

```public class TwoSumProblem {

public static void main(String[] args) {
int[] arr = {10,-2,5,3,1,7,4};

twoSumArray(arr,8);
}

public static void twoSumArray(int[] arr, int i) {

//		sort the array using Arrays  sort

Arrays.sort(arr);
int size = arr.length;
int left = 0;
int right =size-1;
List<Integer> list = new ArrayList<Integer>();

while(left<right) {
int diff = arr[left]+arr[right];
if(diff<i) {
left++;
}else if(diff>i) {
right--;
}else {
left++;
right--;
}
}

for(Integer it : list) {
System.out.println(it);
}
}
```

If you run this program you will get the list of sub set whose sume is equal to 8.