## Find K Complementary numbers from array Java implementation

### 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.

``````
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
*/
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

## Browser automatically sorting json object based on key problem..

### Json data got sorted on browser by its key

This a problem where the browser decides to sort the json you provided its own way rather than the one you sorted.

And it happens especially if you have key value pair in json payload you are passing.

So the scenario would be, there JSON data you are sending from the backend is sorted and you displayed it on front end with some javascript, but the result you are showing is not sorted with the original sorting order you set.

#### Solution

I observed that some browsers, at least Chrome, is doing the sorting in the situation that is discussed above.

For the fix: make the key of the json values you are passing string format rather than number

like

in place of using:
`{1:"one", 4:"four"}`

use

`{"1":"one", "4":"four"}`