Question 1: Find Pair With Given Sum in an Array

Question 1

Given an array of integers, you must find a pair within the array that sums up to a given sum. We assume the array is unsorted.

For example:

Input: 

Array A = {4, 9, 7, 3, 6, 8}

Sum = 11

Output:

Pair found at 0 and  2 (4 +  7)

Pair found at 3 and 5 (3 + 8)

1. Solution 1: Inefficient Solution
2. Solution 2: Start with Sorting
3. Solution 3: Use a hashmap

Solution 1: Inefficient Solution (Quadratic time)

In this solution, we loop through the array and for each element, we calculate the sum with every other element and compare with the given sum. If the sum equals the given sum. We output the indexes.

The Java program is given below:

//Question 1: Given an unsorted array of integers
// find a pair of integers with the given sum in it

package examples;

public class FindPairSum1{
	public static void findPair1(int A[], int sum) {
		
		//loop until element before the last
		for(int i = 0; i< A.length-1; i++) {
			
			//loop until the last element
			for(int j = i+1; j < A.length; j++) {
				
				//if given sum is found, print the indexes
				if(A[i] + A[j] == sum) {
					System.out.println("Pair found at " + i + " and " + j);
				}
			}
		}
	}//End of findPair1
	
	public static void main(String args[]) {
		int ar[] = {3,5,2,8,0,1,11,7};
		int sum = 10;
		findPair1(ar, sum);
	}//End of main		
}

Solution 1: Inefficient Solution – Quadratic Time

Solution 2: Start by Sorting (nlog(n) time)

In this solution, we first sort the array. As such, the largest elements  are are the end of the array while the smallest elements are at the beginning of the array. Then we use two iterators. The first counting from the beginning of the array while the second counting from the end of the array.

For each iteration,  we calculate the sum to check if it equals the given sum

The Java program is given below.

Note: The index returned with this method is the index of the elements in the sorted array which is not the same as the indexes in the original array.

//findPair2: Sorts the array. Maintain two indices of the two end-points
//Complexity: O(nlogn)

package examples;
import java.util.Arrays;
public class FindPairSum2 {

	public static void findPair2 (int A[], int sum) {
		Arrays.sort(A); //First sort the array
		
		int low = 0;
		int high = A.length - 1;
		
		while(low < high) {
			if(A[low] + A[high] == sum) {
				System.out.println("Sum found are " + A[low] + " and " + A[high]);
				low++;
			}
			else if(A[low] + A[high] < sum) {
				low = low + 1;
			}
			else {
				high = high  - 1;
			}
		} //end of while loop
	}
				

	public static void main(String[] args) {
		int ar[] = {3,5,2,8,0,1,11,7};
		int sum = 10;
		findPair2(ar, sum);
	}
}

Solution 2: Maintain two indexes

Solution 3 – Use of HashMap (Linear time O(n))

In this solution, we iterate though the array just once and store each element in a hash set.. For each element, we would check if the complement of the element is already  in the hashset. If it is there, then we have  a sum. If it is not there then we insert it.

The Java implementation is given below.

//Find pair with given sum using a hashma[
package examples;

import java.util.HashMap;
import java.util.Map;

public class FindPairSum3 {
	
	public static void findPair(int A[], int sum) {
		
		Map<Integer, Integer> map = new HashMap<>();
		
		for(int i = 0; i< A.length; i++) {
			
			//if complement is already in map, print the pair
			if(map.containsKey(sum-A[i])) {
				System.out.println("Pair found at " + map.get(sum-A[i]) + " and " + i);
			}
			
			map.put(A[i], i);
			
		}//end of for
		
	}//end for function
	

	public static void main(String[] args) {
		int ar[] = {3, 20, 5, 6,1,9, 7, 22};
		int sum = 29;
		
         findPair(ar, sum);
	}

}

Solution 3 : Using a HashMap