Find the pairs that makes K Complementary in the given array java solution

Find K complementary pairs from the given array

So the problem is, given an array of numbers, you are going to find the pairs whose sum is K.

Say, if you are given `7, 1, 5, 6, 9, 3, 11, -1` and K = 10 then the pairs would be

=> 1 and 9
=> 3 and 7
=> 11 and -1

Here is the O(n) solution for the K complementary problem in java

It turns out, this is not a pure O(n) solution. Can you spot why?

``````
package algorithm;

import java.util.HashMap;
//import java.util.List;
import java.util.Map;

/**
* Algorithm to find the pairs making the K complementary in O(n) complexity
*
* @author http://gullele.com
* @see KComplementaryTest.java - a JUnit test for this class
*/
public class KComplementary {

private Map pairs;

public static void main(String[] args) {
KComplementary kcomp = new KComplementary();
int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
Integer[][] pairs = kcomp.getKComplementaryPairs(10, numbers);

for (Integer[] thePairs : pairs) {
System.out.println(" Pairs are "+thePairs[0] + " and " + thePairs[1]);
}
}

public KComplementary() {
this.pairs = new HashMap();
}

/**
* An algorithm to find the pair from the given array that would sum up the given K
*
* @note - the algorithm would be done in o(n). First it will run through the whole
* numbers and creates a temporary list of pairs in HashMap with
* (value, sum-value).
* @param sum
* @param listOfIntegers
* @return
*/
public Integer[][] getKComplementaryPairs(int sum, int[] listOfIntegers) {

/*
* I could have used the ArrayList assuming the number of pairs we are getting
* is not known, but giving it a little bit of thought, the number of pairs
* is known in advance, at least the maximum we can get is known.
* By not using the Array list, the algorithm would run O(n) rather than
* O(n**2) since ArrayList.add would would be O(n) by itself
*/
//List complementaryPairs = new ArrayList();
Integer[][] complementaryPairs = new Integer[listOfIntegers.length][2];
//First fill up the pairs with the complementary numbers
for (int number : listOfIntegers) { //O(n) complexity
this.pairs.put(number, sum-number);
}

//then filter out the pairs that don't have corresponding complementary number
int index = 0;
for (int number : listOfIntegers) { //O(n) complexity
int complementary = sum - number;
//check if this key exists in the pairs
if ( this.pairs.containsKey(complementary) ) {
//Had I used array List this would have been used
//Integer[] comps = {number, complementary};
complementaryPairs[index][0] = number;
complementaryPairs[index][1] = complementary;
index ++;
}
}
//System.out.println(index);
//Now trim the array since we know the exact record
Integer[][] trimmed = new Integer[index][2];

index = 0;
for (Integer[] item : complementaryPairs) { //O(n) complexity
if (item[0] != null) {
trimmed[index][0] = item[0];
trimmed[index][1] = item[1];
}
index++;
}

//Total complexity O(n)+O(n)+O(n) ==> O(n)

//had I used arrayList this would have been used
//return complementaryPairs.toArray(new Integer[0][0]);
return trimmed;
}
}

```
```

The above solution runs and would do the job without a problem. But it is not linear solution as it claims to be.

I have got another solution that would explain why and comes up with a solution for it. Check it out here

You can see the jUnit for this class also at here

String Ordered Permutation Algorithm Problem

setting JAVA_HOME on mac osx

hello world weblogic – hello world tutorial on weblogic

Passing composite object parameter to jersey in Restful Java web

Hi. HashMap#containsKey method is O(n), so that makes your solution still O(n^2).

Even though in practice HashMap’s #containsKey and #get methods can be really close to O(1), worst case scenario is still O(n), and big-oh notation is about the worst case scenario.

1. gulleman

Thanks a lot mtrad, you are right, I have used Hashmap that would affect performance and I have left it as it is so others can learn as well – here is a new implementation, I appreciate if you review it as well – http://gullele.com/find-complementary-numbers-from-array-java-implementation/