## Find pairs of integers in an array that sum to a value

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

My initial thoughts:
For each element $a$ in the array, we can find its complement $s-a$ in the array and output this pair. To speed up the search, we can use binary search. Therefore we need to sort the array first, $O(n\log n)$. Then for each element, we search for its complement, that’s another $O(n\log n)$. Together it’s still $O(n\log n)$.

My initial codes:

```	public static boolean binarySeach(int[] array, int element) {
int low = 0;
int high = array.length;
while (low <= high) {
int mid = low + (high - low) / 2;
if (element < array[mid])
high = mid;
else if (element > array[mid])
low = mid + 1;
else
return true;
}
return false;
}

public static List<Pair<Integer>> findSum(int[] array, int sum) {
Arrays.sort(array);
List<Pair<Integer>> result = new LinkedList<Pair<Integer>>();
Set<Integer> visited = new HashSet<Integer>();
for (int i = 0; i < array.length; ++i) {
int a = array[i];
if (!visited.contains(a)) {
visited.add(a);
int b = sum - a;
if (binarySeach(array, b)) {
visited.add(b);
result.add(new Pair<Integer>(a, b));
}
}
}
return result;
}

Solution:
public static void printPairSums(int[] array, int sum) {
Arrays.sort(array);
int first = 0;
int last = array.length - 1;
while (first < last) {
int s = array[first] + array[last];
if (s == sum) {
System.out.println(array[first] + "" + array[last]);
++first;
--last;
} else {
if (s < sum)
++first;
else
--last;
}
}
}

Comments: the solution utilizes the state of sorted array and does a two-way search. Therefore after sorting, we only need one scan of the array. Altogether it ‘reduces’ the time complexity to $O(n\log n + n)$.

Advertisements

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

(function(){var c=function(){var a=document.getElementById("crt-232761484");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-232761484",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();

(function(){var c=function(){var a=document.getElementById("crt-1785316766");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1785316766",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();

Like this:Like Loading...

Related
```