Pair with given sum in array

Given an array a[] and a number X, find  two elements or pair with given sum X in array. For example:

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

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

Pair in array with given sum : thought process

Ask some basic questions about the problem, it’s a good way to dig more into 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 sum equal to X?
  • If there can be negative numbers in array?

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 array and hash together to solve a problem?

Find pairs with given sum : 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, These variable are used to traverse array from two ends of array.
  2. While two variables 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 is greater than X, move towards left from end i.e decrease right by 1
  5. Else if sum is less than X,then move towards right from start, i.e increment left
  6. At last, if sum is equal to X, then return (left, right) as pair.

Example

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 pair 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 sum and so add this pair in 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 sum and so add this pair in result array. Also, decrease right by 1.

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

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){
                resultList.add(new Pair(left, right));
                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 a pair of numbers in array with sum X 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.

Find a pair with given sum in array : Without sorting

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?

Additional constraint put on 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 entire array and find all A’s required for each element. Scan array again and check there was B which required current element as A.
To keep track of required A values, we will create an 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 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 sum-max value of 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 array. It will work in languages which 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.

Pairs with given sum : 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])){
                resultList.add(new Pair(pairMap.get(a[i]), 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 learning process of other by sharing your knowledge, please write to us at communications@algorithmsandme.com