Find two numbers that add to a sum in an array in Java

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 Ο(n2). 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.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.