[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 {
				list.add(arr[left]);
				list.add(arr[right]);
				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.

Hope this will help you in your datastructre problem solving.

Thanks for reading.