1
\$\begingroup\$

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());
}
\$\endgroup\$
4
\$\begingroup\$
  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.
\$\endgroup\$
  • \$\begingroup\$ ooooo...indeed typo it should be numbers :-) \$\endgroup\$ – Exploring Mar 25 '18 at 13:23
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
    }
}
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
-3
\$\begingroup\$

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

Arrays.sort(input);
\$\endgroup\$

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.