Gullele's Corner

Find K complementary numbers from the given array

This is another approach to the problem that I have done it here. On that post, a good deal of visitors pointed out that it is actually o(n*n) not o(n) as I claimed.

Yes, the naive usage of Hashmap for holding the numbers has soared the performance and I have changed the approach as follows.

To remind the k complementary problem and its solution, you are given array of numbers and a number k of which you are going to find numbers that give k complementary. The following is an example of it.

The problem is, given numbers like 7, 1, 5, 6, 9, 3, 11, -1 and given number 10, write a script that would print numbers that would add to 10. In the example, it would be like
7 and 3, 1 and 9, -1 and 11.

Thanks Reda and mtrad for your correction.

package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * Algorithm to find the pairs making the K complementary in O(n) complexity
 * 
 * @author http://gullele.com
 */
public class KComplementary2 {
	
	public static void main(String[] args) {
		KComplementary2 kcomp = new KComplementary2();
		int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
		
		for (Integer number : kcomp.getKComplementaryPairs(10, numbers)) {
			System.out.println(" Pairs are "+ number + " and " + (10-number));
		}
	}
	
	public KComplementary2() {}
	
	/**
	 * 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)+o(nlogn). 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 List getKComplementaryPairs(int sum, int[] listOfIntegers) {
		
		/*
		 * The algorithm works using front and last pointers on ascendingly sorted array. The front would be 
		 * instantiated with 0 and last with length-1; if the arr[front]+arr[last] == sum, then pick
		 * the numbers and add them to the pair array.
		 * if their sum is greater than sum, it means time to check the  second higher number that is lower
		 * than the current highest number. And the reverse would hold true if the sum is less than the sum
		 * time to move to the next higher number from the lower side.
		 */
		if (listOfIntegers == null || listOfIntegers.length == 0) {
			return null;
		}
		
		//quick sort the array 
		quickSort(0, listOfIntegers.length-1, listOfIntegers);
		
		int[] sortedArray = listOfIntegers;
		
		//holder for the complementary pairs
		List pairs = new ArrayList();
		int frontPointer = 0;
		int lastPointer = sortedArray.length-1;
		
		while (frontPointer < lastPointer) {
			int currentSum = sortedArray[frontPointer] + sortedArray[lastPointer];
			if (currentSum == sum) {
				/*
				 * Since sum is found, increment front and decrement last pointer
				 * Only one number is required to be hold, the other can be found 
				 * from sum-number since complementary 
				 */
				pairs.add(sortedArray[frontPointer]);//adding is o(1)
				frontPointer++;
				lastPointer--;
			} else if (currentSum > sum) {
				lastPointer--;
			} else {
				frontPointer++;
			}
		}
		
		return pairs;
	}
	
	/**
	 * sort the numbers. I have used quick sort here. QuickSort is nlogn in average case 
	 * well, in worst case it still would be n**2 though :(
	 * @param numbers
	 * @return sorted array numbers.
	 */
	public void quickSort(int lowerIndex, int higherIndex, int[] numbers) {
		/*
		 * Recursively inarray sort. Start from arbitrary value to compare from and recursively sort its 
		 * left and right.
		 */
		int pivot = lowerIndex+(higherIndex-lowerIndex)/2;
		int lower = lowerIndex;
		int higher = higherIndex;
		
		while (lower < higher) {
			while (numbers[lower] < numbers[pivot]) {
				lower++;
			}
			while (numbers[higher] > numbers[pivot]) {
				higher--;
			}
			
			//swap those needed to be on the left on those on the right.
			if (lower <= higher) {
				int temp = numbers[lower];
				numbers[lower] = numbers[higher];
				numbers[higher] = temp;
				lower++;
				higher--;
			}
		}
		if (lowerIndex < higher) {
			quickSort(lowerIndex, higher, numbers);
		}
		
		if (lower < higherIndex) {
			quickSort(lower, higherIndex, numbers);
		}
	}
}

Love algorithms? See how you would solve the following

Can you find the three numbers that would sum to T from given array?

From a file of billion numbers, find missing numbers with limited memory