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

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.add(comps); //this is O(n)
				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

J2EE Maven Eclipse Hello World Tutorial Part Two

Check if two strings are anagrams or not

Java Tomcat error: can not access a member of class with modifiers

pass all the jars in classpath when compiling java

Find K Complementary numbers from array Java implementation

Find longest palindrom from sequence of characters

2 Comments
  1. mtrad

    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/

Leave a Reply

Your email address will not be published. Required fields are marked *

*
*