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

Sorting array by two fields in PHP

assume you have the following array:

$arr=array(
	array('field1'=>108, 'field2'=>'some'),
	array('field1'=>200, 'field2'=>'zen'),
	array('field1'=>105, 'field2'=>'bar'),
	array('field1'=>100, 'field2'=>'foo'),
	array('field1'=>200, 'field2'=>'yellow'),
	array('field1'=>200, 'field2'=>'any'),
);
How would you approach if you want to sort the array first by field1 and then by field2. That is sort the array by field1 but for field1 values that are same, sort by field two.. just like the SQL equivalent of ORDER By column1, colum2..

usort($arr, function($a, $b){
	if ($a['field1']>$b['field1']){
		return 1;
	}elseif($a['field1']<$b['field1']){
		return -1;
	}else{
		return strcasecmp($a['field2'], $b['field2']);
	}
});

Array Merging in PHP preserving keys. array_merge reindexing arrays

Merging arrays in php keeping the keys

Say you have two arrays with the following values in them:


$array1 = array(13=>'bad luck', 7=>'billion people');
$array2 = array(1=>'number');

And you want the final result to be


$final = (1=>'number', 13=>'billion people', 13=>'bad luck');

But when you merge arrays and using array_merge, u got the indexes being ripped out from the second or first array whose keys are numeric?

The result using array_merge would be

(0 => 'bad luck', 1 => 'billion people', 2 => 'number')

And you don’t want that

Here is a simple way – just use operator overloading of the plus sign

$array1 = array(13=>'bad luck', 7=>'billon population');
$array2 = array(1=>'number');
$merged = $array1 + array2;

Note: This is provided the keys are not overlapping, otherwise, the first array would take ownership of keeping the value.

Do you know how to run single phpunit test

Know who is calling your php script browser or script?