# 2 Sum problem

Tags: , , ,

2 sum problem goes like: given an array a[] and a number X, find two elements or pair with given sum X in the array. For example:

```Given array : [3,4,5,1,2,6,8] X = 10
The answer could be (4,6) or (2,8).
```

Before looking at the post below, we strongly recommend to have a pen and paper and git it a try to solve it.

## Thought process

Ask some basic questions about the problem, it’s a good way to dig more into the problem and gain more confidence. Remember interviewers are not trained interrogators, they slip hint or two around solution when you ask relevant questions.

• Is it a sorted array? If not, think additional complexity you would be adding to sort it
• If duplicates present in array?
• Whether returning first pair is enough or should we return all such pairs with a sum equal to X?
• If there can be negative numbers in array?

Watch out the video here:

This problem is used regularly in interviews because it tests so many things about your programming knowledge.
It validates that if you can traverse array properly, with both lower and higher bounds. It also checks your optimizing ability once you got a working solution. Can you work with additional constraints? Are you able to work with more than one data structure like an array and hash together to solve a problem?

## 2 sum problem using sorting

Let’s go with an assumption that input is sorted array and if not, we will sort it? If you want to know how to sort an array efficiently,refer Quick sort or Merge sort
With sorted array, we can apply below algorithm to find a pair with given sum.

```1. Initialize two variable left = 0 and right = array.length-1
2. While left and right do not cross each other,
3. Get sum of elements at index left and right, i.e A[left] + A[right]
4. If sum > K, move towards left from end i.e decrease right by 1
5. Else if sum < K,then move towards right from start, i.e increment left
6. At last, if sum is equal to K, then return (left, right) as pair.
```

Let’s see how this works with an example and then we will implement it. Given an array as shown and sum = 17, find all pairs which sum as 17.

Initialization step, left = 0 and right = array.length – 1

A[left] + A[right] = 20 which is greater than sum (17), move right towards left by 1.

Again, A[left] + A[right] = 18 which is greater than sum (17), move right towards left by 1.

At this point, A[left] + A[right] is less than sum(17), hence move left by 1

Now, A[left] + A[right]  is equal to the sum and so add this pair in the result array. Also, decrease right by 1, why?

At this point, A[left] + A[right] is less than sum(17), hence move left by 1

Again, A[left] + A[right] is less than sum(17), hence move left by 1

A[left] + A[right]  is equal to the sum and so add this pair in the result array. Also, decrease right by 1.

Since left and right point to the same element now, there cannot be a pair anymore, hence return.

### Show me the implementation

```package com.company;

import javafx.util.Pair;

import java.util.ArrayList;

/**
* Created by sangar on 5.4.18.
*/
public class PairWithGivenSum {
public static ArrayList<Pair<Integer, Integer>> pairWithGivenSum(int[] a, int sum){
int left = 0;
int right = a.length - 1;

ArrayList<Pair<Integer, Integer>> resultList = new ArrayList<>();

while(left < right){
/*If sum of two elements is greater than
sum required, move towards left */
if(a[left] + a[right] > sum) right--;
/*
If sum of two elements is less than
sum required, move towards right
*/
if(a[left] + a[right] < sum) left++;
if(a[left] + a[right] == sum){
right--;
}
}
return resultList;
}
public static void main(String[] args) {
int a[] = new int[] {10, 20, 30, 40, 50};

ArrayList<Pair<Integer, Integer>> result = pairWithGivenSum(a,50);
for (Pair<Integer, Integer> pair : result ) {
System.out.println("("+ pair.getKey() + "," + pair.getValue()  + ")");
}
}
}
```

Complexity of this algorithm to find two numbers in array with sum K is dependent on sorting algorithm used. If it is merge sort, complexity is O(n log n) with added space complexity of O(n). If quick sort is used, worst case complexity is O(n2) and no added space complexity.

## Solution with hashmap

In first method,  array is modified, when it is not already sorted. Also, Preprocessing step (sorting) dominates the complexity of algorithm. Can we do better than `O(nlogn)` or in other words, can we avoid sorting?

An additional constraint put on the problem is that you cannot modify original input.  Use basic mathematics, if A + B = C, then A = C-B.  Consider B is each element for which we are looking for A. Idea is to scan the entire array and find all A’s required for each element. Scan array again and check there was B which required the current element as A.
To keep track of required A values, we will create a hash, this will make second step O(1).
We can optimize further by scanning array only once for both steps.

1. Create an hash
2. Check element at each index of array
2.a If element at current index  is already in hash. return pair of current index and value in hash
2.b If not, then subtract element from sum and store (sum-A[index], index) key value pair in hash.

This algorithm scans the array only once and does not change input. Worst-case time complexity is O(n), hash brings additional space complexity. How big should be the hash? Since all values between the sum-max value of the array and sum-min value of array will be candidate A’s hence hash will be of difference between these two values.

This solution does not work in C if there are negative numbers in an array. It will work in languages that have HashMaps in-built. For C, we have to do some preprocessing like adding absolute of smallest negative number to all elements. That’s where our fourth question above helps us to decide.

### 2 sum problem hash based implementation

```package com.company;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;

/**
* Created by sangar on 5.4.18.
*/
public class PairWithGivenSum {
public static ArrayList<Pair<Integer, Integer>> pairsWithGivenSum2(int[] a, int sum){
int index = 0;
ArrayList<Pair<Integer, Integer>> resultList = new ArrayList<>();

HashMap<Integer, Integer> pairMap = new HashMap<>();
for(int i=0; i< a.length; i++){
if(pairMap.containsKey(a[i])){
}
pairMap.put(sum-a[i], i);
}
return resultList;
}
public static void main(String[] args) {
int a[] = new int[] {10, 20, 30, 40, 50};

ArrayList<Pair<Integer, Integer>> result = pairsWithGivenSum2(a,50);
for (Pair<Integer, Integer> pair : result ) {
System.out.println("("+ pair.getKey() + "," + pair.getValue()  + ")");
}
}
}
```

Please share if there is some error or suggestion to improve. We would love to hear what you have to say. If you want to contribute to the learning process of others by sharing your knowledge, please write to us at [email protected]