trjhtr

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

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.

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

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;
 

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

Arrays.sort(input);