2
\$\begingroup\$

I came up with the following solution.

  1. Is there a better way to solve this problem than the proposed?
  2. Also I used LinkedList to convey the result back to the API caller. Is there a better data structure to use?
  3. I tried using a 2 dimensional array to store the pairs, but int creation requires a size, which we are not aware of until we evaluate the array. So I had to use a LinkedList where the size can be dynamic.
public class FindPairsInAnArrayAddingToASum {

    private static class ResultPair{
        ResultPair prev;
        ResultPair next;
        int a;
        int b;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] items = new int[]{1,2,3,4,5,5,6,7};
        System.out.println("Pairs: ");
        ResultPair currentNode = getPairsAddingToSum(items, 10);
        while(currentNode != null){
            System.out.println("--> "+currentNode.a+", "+currentNode.b);
            currentNode = currentNode.next;
        }
    }

    public static ResultPair getPairsAddingToSum(int[] items, int prescribedSum){
        ResultPair headNode = null;
        ResultPair currentNode = null;

        //Sort the array
        Arrays.sort(items);

        //Introduce left and right pointers
        int left = 0;
        int right = items.length-1;

        //Navigate from both directions
        while(left < right){
            if(items[left] + items[right] == prescribedSum){

                currentNode = addThePair(items[left], items[right], currentNode);

                //Save the head - Only the first time a node is created
                if(headNode == null)
                    headNode = currentNode;

                //Increment left and decrement right
                left++;
                right--;

            }else if(items[left] + items[right] < prescribedSum){
                left++;
            }else{
                right--;
            }
        }

        return headNode;
    }

    public static ResultPair addThePair(int a, int b, ResultPair currentNode){
        ResultPair newNode = new ResultPair();
        newNode.a = a;
        newNode.b = b;
        if(currentNode != null){
            currentNode.next = newNode;
            newNode.prev = currentNode;
        }
        return newNode;
    }

}
\$\endgroup\$

migrated from stackoverflow.com Aug 13 '17 at 19:56

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ Question: are all the numbers guaranteed to be unique? If not, how are you supposed to deal with duplicate numbers: ignore them or print duplicate answers? \$\endgroup\$ – JS1 Aug 13 '17 at 20:52
  • \$\begingroup\$ Duplicates allowed in the input array. The example used has duplicate 5 in it. \$\endgroup\$ – AKh Aug 13 '17 at 21:42
  • 1
    \$\begingroup\$ If the sum were 11 instead of 10, would you be required to print out 5,6 twice or just once? Perhaps you could either add the actual question or a link to it. \$\endgroup\$ – JS1 Aug 14 '17 at 2:08
  • \$\begingroup\$ If you need to output duplicates this can fail. \$\endgroup\$ – paparazzo Aug 14 '17 at 15:35
3
\$\begingroup\$

I like your approach with the two-pointer-array. As for the performance: The other answers here use the Big O notation as a basis for comparing the speed of different algorithms, hinting that using a HashMap or a HashSet might be faster than your approach. But this is misleading, since the Big O notation says nothing about the speed of different algorithms compared to each other, but only about how much slower an algorithm will be when \$n\$ increases. For example, you might have an \$O(n)\$ algorithm that takes \$n\$ hours to complete, and an \$O(n^{2})\$ algorithm that takes \$n^{2}\$ milliseconds to complete, and the second algorithm will be faster for all \$n < 3600000\$. Of course, this is an extreme example, I just wanted to make a principle clear.

As for this case, I tried to compare your algorithm with the algorithm suggested by zenwraight. Here is my implementation of that algorithm:

public class FindPairsInAnArrayAddingToASum {
    public static class IntegerPair {
        public final int number1;
        public final int number2;

        public IntegerPair(int number1, int number2) {
            this.number1 = number1;
            this.number2 = number2;
        }
    }

    public static List<IntegerPair> findNumberPairs(int[] items, int prescribedSum) {
        Map<Integer, Integer> frequencies = new HashMap<>();
        for (int item : items) {
            Integer previousFrequency = frequencies.get(item);
            frequencies.put(
                    item,
                    previousFrequency != null
                    ? previousFrequency + 1
                    : 1);
        }

        List<IntegerPair> result = new LinkedList<>();
        for (int item : frequencies.keySet()) {
            int complement = prescribedSum - item;
            Integer complementFrequency = frequencies.get(complement);
            if (complementFrequency != null
                    && (item != complement || complementFrequency > 1)) {
                result.add(new IntegerPair(item, complement));
            }
        }

        return result;
    }
}

First, I benchmarked 10 test cases where every array contains 10,000 random integers, with a different random prescribed sum for every array. Here are the results:

Double pointer array: 0.022 seconds
Hash map: 0.066 seconds

Double pointer array: 0.012 seconds
Hash map: 0.036 seconds

Double pointer array: 0.017 seconds
Hash map: 0.021 seconds

Double pointer array: 0.003 seconds
Hash map: 0.071 seconds

Double pointer array: 0.006 seconds
Hash map: 0.013 seconds

Double pointer array: 0.006 seconds
Hash map: 0.009 seconds

Double pointer array: 0.008 seconds
Hash map: 0.01 seconds

Double pointer array: 0.003 seconds
Hash map: 0.009 seconds

Double pointer array: 0.003 seconds
Hash map: 0.007 seconds

Double pointer array: 0.002 seconds
Hash map: 0.008 seconds

So your code performed slightly better in all test cases listed here (although there also were some 10,000-size array test cases in other benchmark runs where the HashMap performed slightly better). Next, 10 test cases, same as above, but now the arrays contain 100,000 integers:

Double pointer array: 0.064 seconds
Hash map: 0.346 seconds

Double pointer array: 0.068 seconds
Hash map: 0.381 seconds

Double pointer array: 0.03 seconds
Hash map: 0.068 seconds

Double pointer array: 0.032 seconds
Hash map: 0.12 seconds

Double pointer array: 0.032 seconds
Hash map: 0.17 seconds

Double pointer array: 0.037 seconds
Hash map: 0.073 seconds

Double pointer array: 0.014 seconds
Hash map: 0.12 seconds

Double pointer array: 0.013 seconds
Hash map: 0.054 seconds

Double pointer array: 0.016 seconds
Hash map: 0.059 seconds

Double pointer array: 0.014 seconds
Hash map: 0.066 seconds

Your code still wins. The differences are even more significant in some cases than when the arrays only contained 10,000 integers. Next, increase the array size to 1,000,000 integers:

Double pointer array: 0.495 seconds
Hash map: 2.356 seconds

Double pointer array: 0.336 seconds
Hash map: 3.916 seconds

Double pointer array: 0.279 seconds
Hash map: 0.651 seconds

Double pointer array: 0.164 seconds
Hash map: 0.713 seconds

Double pointer array: 0.162 seconds
Hash map: 0.885 seconds

Double pointer array: 0.31 seconds
Hash map: 0.868 seconds

Double pointer array: 0.164 seconds
Hash map: 0.795 seconds

Double pointer array: 0.165 seconds
Hash map: 0.919 seconds

Double pointer array: 0.323 seconds
Hash map: 0.71 seconds

Double pointer array: 0.164 seconds
Hash map: 0.697 seconds

Your double pointer array beats the hash map again. Finally, increase the array size to 5,000,000 (the program ran out of memory when I tried to run it with 10,000,000-size arrays, probably because I generated all 10 test cases in advance instead of only generating one for each benchmark).

Double pointer array: 1.625 seconds
Hash map: 14.116 seconds

Double pointer array: 0.927 seconds
Hash map: 12.554 seconds

Double pointer array: 0.914 seconds
Hash map: 11.51 seconds

Double pointer array: 0.924 seconds
Hash map: 10.654 seconds

Double pointer array: 1.013 seconds
Hash map: 15.335 seconds

Double pointer array: 1.039 seconds
Hash map: 10.512 seconds

Double pointer array: 0.9 seconds
Hash map: 11.928 seconds

Double pointer array: 0.954 seconds
Hash map: 10.16 seconds

Double pointer array: 0.916 seconds
Hash map: 12.326 seconds

Double pointer array: 0.899 seconds
Hash map: 9.881 seconds

I don't know why the HashMap algorithm takes so long here. It could have to do with the need to increase the capacity of the HashMap multiple times, but experimenting with different values for the initial capacity didn't make much of a difference. But anyway, I think this makes it clear that you shouldn't rely on the Big O notation when comparing the speed of different algorithms to each other.

However, apart from the performance, your public method getPairsAddingToSum(int[], int) returns a ResultPair, which is a private class, so whoever calls your method won't be able to do anything with the returned value. But regardless of that, I don't understand why, in your code, you invent something that already exists, namely a linked list. Why don't you just use java.util.LinkedList?

In any case, you also asked whether there would be a better data structure than a linked list to return the found pairs. I think there is, namely a Set. After all, the array might contain duplicates, so it might also contain duplicate valid pairs. Of course, in order to take advantage of a Set, you would have to implement hashCode() and equals(Object) in your ResultPair class (which would then only contain the two integers and no nodes). Seeing as, in your algorithm, the first number in a pair will always be less than or equal to the second number, it would suffice for ResultPair.equals(Object) to compare a and b from both ResultPairs to each other without sorting them first, thereby considering to ResultPairs with the same numbers but in a different order unequal, but this depends on how you want to use the class ResultPair further (in case you do want to use it outside the context of this algorithm). Note that, if you use a Set, the algorithm will naturally take longer than if you use a List, because removing duplicates is an additional task that was not carried out in your original code.

Edit:

Actually, there's a much simpler and more efficient approach for avoiding duplicate number pairs than using a Set: When adjusting the array counters for the next while loop, you could simply in-/decrement them until the integer they point to is different from the integer they previously pointed to, instead of in-/decrementing them only once.

\$\endgroup\$
2
\$\begingroup\$

Well you can solve this problem with O(n) time using a set , just store all the elements of the array in a set , then loop over them again and check if the result of subtracting the element of the array from the given sum exist in the set , if so and the element of the array not equals to half of the given sum then you got yourself a pair( element, sum- element) , if the element equals half of the sum you need to count how many times the element exists in the array , you will have pairs (element, element) with the number of repetition of this element -1.

\$\endgroup\$
  • \$\begingroup\$ Isn't my solution O(N) time? I think it is. Anyways thanks for the idea. But your solution would require O(N) space in worst case. \$\endgroup\$ – AKh Aug 13 '17 at 20:15
  • \$\begingroup\$ I did not go into details of your algorithm , but you are sorting using merge sort , thats alone O(nlogn) \$\endgroup\$ – Amer Qarabsa Aug 13 '17 at 20:19
  • \$\begingroup\$ set.retainAll(set.stream().map(i -> sum - i).collect(Collectors.toSet())); \$\endgroup\$ – toto2 Aug 14 '17 at 14:36
  • \$\begingroup\$ set.stream().map(i -> new Pair(i, sum -i)).collect(Collectors.toSet()); \$\endgroup\$ – toto2 Aug 14 '17 at 14:37
  • \$\begingroup\$ Java is very verbose. In more modern languages that could have been just a few characters. \$\endgroup\$ – toto2 Aug 14 '17 at 14:37
2
\$\begingroup\$

@AKh the time complexity of your algorithm is \$O(nlogn)\$ because by default java makes use of Tim Sort, I guess not sure about it.

But you can solve this problem in \$O(n)\$ time be making use of HashMap.

Algorithm:

  1. Iterate through the array once and store the elements in the array as A[i] -> number of occurrences.
  2. Now that you have count of each element, iterate through it again and check if difference between required sum number and current array element, exists in our HashMap or not and if yes the count of the array element will give you number of pairs.

Hope this helps!

\$\endgroup\$
  • \$\begingroup\$ This approach cannot be used if there is a restriction on Space Complexity. Set or HashMap approach requires additional space O(N) \$\endgroup\$ – AKh Aug 16 '17 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.