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

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 {
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());
}


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.
• ooooo...indeed typo it should be numbers :-) Commented Mar 25, 2018 at 13:23

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.

Incorporating the feedbacks, here is the answer

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 {
high--;
low++;
}
}

return pairs;
}
}


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 {
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;
}


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

Arrays.sort(input);