Find all pairs in an array that sum to a given number without using HashMap

Question

Find all pairs in an array that sum to a given number without using HashMap. Duplicate pairs are not allowed. Input array cannot be modified.

input: {-2, -1, -1, 5, 7, 7, 7, 7, 8}, target = 7

output: (-1, 8)

As it is mentioned, using HashMap is not allowed, so I decided to use binary search.

GitHub

public class TwoSumProblemUsingBinarySearch {

    public static class Pair {

        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object other) {
            if (other instanceof Pair) {
                Pair o = (Pair) other;
                return this.x == o.x && this.y == o.y;
            }

            return false;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    public static Set<Pair> findAllParis(int input[], int target) {
        int numbers[] = Arrays.copyOf(input, input.length);
        Set<Pair> pairs = new HashSet<>();

        Arrays.sort(numbers);

        for (int low = 0, high = input.length - 1; low < high; ) {
            int sum = input[low] + input[high];

            if (sum > target) {
                high--;
            } else if (sum < target) {
                low++;
            } else {
                pairs.add(new Pair(input[low], input[high]));
                high--;
                low++;
            }
        }

        return pairs;
    }
}

@Test
public void findAllParis() throws Exception {

    System.out.println(TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7));
    assertEquals(1, TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7).size());
}

Answer 1

1. Typo in method name as pointed out by @Stingy. Should be findAllPairs.
2. Accessing wrong array: You are reading values from input instead of your sorted copy numbers. This is probably a typo. E.g. int sum = input[low] + input[high]; should be int sum = numbers[low] + numbers[high];

3. Your for loop has an empty update statement, this isn't wrong per-se but a bit unusual. Consider an alternative using while instead:

   int low = 0, high = numbers.length-1;
   while (low < high) {
       int sum = numbers[low] + numbers[high];
       //...
   }
   

4. Insufficient test: As evidenced by its failure to catch the bug in 2. the test is too limited to be of much help. Consider checking more than one example (especially corner-cases like an empty input array) and checking against the expected output instead of just its size.

Answer 2

You can prevent duplicate pairs by incrementing/decrementing your counters not only once, but until they point to a number that is greater/lesser than the number they previously pointed to. That way, you can store the pairs in a List instead of a Set, which will probably be faster, because the List doesn't need to check whether it already contains a pair that is equal to the one being added.

Also, there is a typo in your method names findAllParis.

Answer 3

Incorporating the feedbacks, here is the answer

Github: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/TwoSumProblemUsingBinarySearch.java#18

public class TwoSumProblemUsingBinarySearch {

    public static class Pair {
        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object other) {
            if (other instanceof Pair) {
                Pair o = (Pair) other;
                return this.x == o.x && this.y == o.y;
            }

            return false;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    public static Set<Pair> findAllPairs(int input[], int target) {
        int numbers[] = Arrays.copyOf(input, input.length);
        Set<Pair> pairs = new HashSet<>();

        Arrays.sort(numbers);

        for (int low = 0, high = numbers.length - 1; low < high; ) {
            int sum = numbers[low] + numbers[high];

            if (sum > target) {
                high--;
            } else if (sum < target) {
                low++;
            } else {
                pairs.add(new Pair(input[low], input[high]));
                high--;
                low++;
            }
        }

        return pairs;
    }
}

Answer 4

You can avoid creating pairs that will be discarded as duplicates. Just advance to the next different value instead of simply the next value here:

            pairs.add(new Pair(input[low], input[high]));
            high--;
            low++;

then becomes

            pairs.add(new Pair(numbers[low], numbers[high]));
            for (final int n = numbers[high--];  low < high && numbers[high] == n;  --high)
                ;
            for (final int n = numbers[low++];   low < high && numbers[low]  == n;  ++low)
                ;

And then we can use a plain list instead of a set:

public static List<Pair> findAllPairs(int input[], int target) {
    int numbers[] = Arrays.copyOf(input, input.length);
    Arrays.sort(numbers);

    ArrayList<Pair> pairs = new ArrayList<>();
    for (int low = 0, high = input.length - 1;  low < high;  ) {
        int sum = numbers[low] + numbers[high];

        if (sum > target) {
            --high;
        } else if (sum < target) {
            ++low;
        } else {
            pairs.add(new Pair(numbers[low], numbers[high]));
            for (final int n = numbers[high--];  low < high && numbers[high] == n;  --high)
                ;
            for (final int n = numbers[low++];   low < high && numbers[low]  == n;  ++low)
                ;
        }
    }

    return pairs;
}

Answer 5

You would also have to add this to the findAllPairs method to sort the initial list which is the input:

Arrays.sort(input);