**Problem: **Write a Java program to find two numbers that add to a sum in an array. A solution of time complexity Ο(n) is expected.

Example: If the input array is { 2, 4, 1, 6, 2, 9, 6, 7, -3 } and the given sum is 16 then output should be 9, 7.

Solution should return at least one pair of numbers which add up to given sum.

Obvious approach is to run two loops and find two numbers that add up to a sum.

In first loop we pick an element of the input array one-by-one and then in second loop again we pick element one-by-one until we find a pair which add up to given sum.

But in worst-case, run-time of this approach will be **Ο(n ^{2})**. We want an algorithm whose run-time is Ο(n).

## Algorithm to find two numbers that add to a sum in an array

Say the input array is A with n elements. Let S be the sum. 1. Create frequency map for the elements A Frequency map holds elements of array with their respective frequencies in the array. Ex: If the input array is {2, 3, 2, 4, 6} then, frequency map would look like {2->2, 3->1, 4->1, 6->1} 1. Let M be the frequency map. 2. Iterate over the elements of A for i = 0 to n If M contains A[i] Add A[i] to M and increase value of A[i] by 1 Else Add A[i] to M with value 1 End if End for 2. Iterate over entries of frequency map, M while M has entries entry = M.entry firstNumber = entry.key secondNumber = S - firstNumber // Expected second number If M contains secondNumber If firstNumber != secondNumber return {firstNumber, secondNumber} End if // If an element is present more than once in input // If S= 12, and if 6 present twice or more then // following condition takes care of that If frequency of secondNumber is more than 1 in M return {firstNumber, secondNumber} End if End if End while

**Analysis:**

Let us analyze above algorithm.

1. In step 1 we create a frequency map. We iterate over the elements of the array. So the run-time of this step id Ο(n).

2. In step 2, we iterate over the map entries. Map can have maximum n entries if all the elements in the input array are unique. So the worst-case run-time of this step is Ο(n).

So the total run-time = Ο(n) + Ο(n) = 2Ο(n). 2 is constant, so the run-time of this algorithm is **Ο(n)**.

**Java program:**

We will implement above algorithm in Java.

package com.javafries.array; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.Map; import java.util.Map.Entry; public class PairProblem { private static int[] findPairs(int[] arr, int sum) { if (arr.length < 2) throw new RuntimeException("Input array size is less than 2."); Map<Integer, Integer> frequencyMap = createElementFrequencyMap(arr); Iterator<Entry<Integer, Integer>> iterator = frequencyMap.entrySet() .iterator(); while (iterator.hasNext()) { int firstNumber = iterator.next().getKey(); int secondNumber = sum - firstNumber; if (frequencyMap.containsKey(secondNumber)) { if (firstNumber != secondNumber) return new int[] { firstNumber, secondNumber }; if (frequencyMap.get(secondNumber) > 1) return new int[] { firstNumber, secondNumber }; } } throw new RuntimeException( "There are no two elements in the array which sum up to " + sum); } private static Map<Integer, Integer> createElementFrequencyMap(int[] arr) { Map<Integer, Integer> frequencyMap = new LinkedHashMap<Integer, Integer>(); for (int key : arr) { if (frequencyMap.containsKey(key)) frequencyMap.put(key, frequencyMap.get(key) + 1); else frequencyMap.put(key, 1); } return frequencyMap; } public static void main(String[] args) { int[] arr = { 2, 4, 1, 6, 2, 9, 6, 7, -3 }; int sum = 16; try { int[] pair = findPairs(arr, sum); System.out.println("Two numbers that add up to a sum = " + sum + " in the array are : " + pair[0] + ", " + pair[1]); } catch (RuntimeException ex) { System.out.println(ex.getMessage()); } } }

**Output:**

Two numbers that add up to a sum = 16 in the array are : 9, 7

I hope you liked and understood above solution.

Your questions and comments are most welcome.