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};
	public static void twoSumArray(int[] arr, int i) {
//		sort the array using Arrays  sort
		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) {
			}else if(diff>i) {
			}else {
		for(Integer it : list) {

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.

1 comment:

  1. JT Marriott International to open JT Marriott International Casino
    JT Marriott International Casino, the premier entertainment destination in 천안 출장안마 the 안성 출장샵 Caribbean for the first 군산 출장안마 time, is set 안동 출장안마 to 제주 출장마사지 rebrand from the