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

Question

Assume you have an array of random integers and a sum value. Find all pairs of numbers from the array that sum up to the given sum in O(n) time. Find all distinct pairs. (1,2) and (2,1) are not distinct.

import java.util.HashSet;

public class PairsSummingToElement {

  public static void main(String[] args) {
    PairsSummingToElement e = new PairsSummingToElement();
    int[] input = new int[] { 2, 5, 3, 7, 9, 8 };
    int sum = 11;
    HashSet<Pair> result = e.findAllPairs(input, sum);
    for (Pair p : result) {
      System.out.println("(" + p.getElement1() + "," + p.getElement2() + ")");
    }

  }

  public HashSet<Pair> findAllPairs(int[] inputList, int sum) {
    HashSet<Integer> allElements = new HashSet<Integer>();
    HashSet<Integer> substracted = new HashSet<Integer>();
    HashSet<Pair> result = new HashSet<Pair>();

    for (int i : inputList) {
      allElements.add(i);
      substracted.add(i - sum);
    }

    for (int i : substracted) {
      if (allElements.contains(-1 * i)) {
        addToSet(result, new Pair(-i, i + sum));
      }
    }

    return result;

  }

  public void addToSet(HashSet<Pair> original, Pair toAdd) {
    if (!original.contains(toAdd) && !original.contains(reversePair(toAdd))) {
      original.add(toAdd);
    }
  }

  public Pair reversePair(Pair original) {
    return new Pair(original.getElement2(), original.getElement1());
  }

}

class Pair {
  private int element1;

  private int element2;

  public Pair(int e1, int e2) {
    element1 = e1;
    element2 = e2;
  }

  public int getElement1() {
    return element1;
  }

  public int getElement2() {
    return element2;
  }

  public int hashCode() {
    return (element1 + element2) * element2 + element1;
  }

  public boolean equals(Object other) {
    if (other instanceof Pair) {
      Pair otherPair = (Pair) other;
      return ((this.element1 == otherPair.element1) && (this.element2 == otherPair.element2));
    }
    return false;
  }

}

Answer 1

No comments on the time complexity, I do have a bunch of other comments:

Code to interfaces, not implementations

It's better to use Set<Integer> allElements = new HashSet<Integer>() (side note: guess you're not on >= Java 7, since you can use diamond operators otherwise) so that users of allElements do not need to know that it actually is a HashSet. This is just good practice. The lesson here is that it allows the programmer to replace the implementation with another in the future when required.

Does not contain, then add to a Set

In the following code block:

if (!original.contains(toAdd) && !original.contains(reversePair(toAdd))) {
  original.add(toAdd);
}

I think the extra check !contains() is not really required because Set.add()'s Javadoc says:

If this set already contains the element, the call leaves the set unchanged and returns false.

So, even if original did contain toAdd, calling add() will leave the set unchanged anyways. I guess this is useful when you're running on a large set of inputs so that there is some short-circuiting done, hence this is strictly just 'food-for-thought' and not something to frown upon.

hashCode()

I'm guess there's an implied range of inputs such as all must be positive right? Because your calculation (element1 + element2) * element2 + element1 will yield the same hash codes when element1 + element2 equals to 1, and having a bunch of negative and positive integers (or just 0, 1) will 'break' this easily. You may want to update your question with any assumptions on the range of inputs.

How to reverse a Pair

I think that you can move your method reversePair(Pair) into the Pair class itself as such:

public final class Pair { // also declared as final

    private final int element1; // also declared as final
    private final int element2; // also declared as final

    public Pair(int element1, int element2) {
        this.element1 = element1;
        this.element2 = element2;
    }
    ...

    public Pair getReverse() {
        return new Pair(element2, element1);
    }
}

Using it then becomes slightly easier:

if (!original.contains(toAdd.getReverse())) {
  original.add(toAdd);
}

Override toString()

Oh yeah, given how you want to print the contents of Pair objects in the end, why not just override toString() too? :)

Answer 2

This is on top of what @h.j.k. already said very well.

The addToSet and reversePair don't really make this code easier to understand. The logic of the substracted set, and the manipulations with signs are confusing. A simpler logic is possible:

• Put all the numbers in a set (you already do this)
• For each number num:
  • If sum - num is in the set, and sum - num was not already used, then:
  • Add num to the set of used numbers
  • Add the pair (num, sum - num)

Implemented this way, it looks simpler to me than the original:

public Set<Pair> findAllPairs(int[] inputList, int sum) {
    Set<Integer> numbers = new HashSet<>(inputList.length);
    for (int num : inputList) {
        numbers.add(num);
    }

    Set<Integer> usedNumbers = new HashSet<>();
    Set<Pair> pairs = new HashSet<>();
    for (int num : inputList) {
        int pair = sum - num;
        if (numbers.contains(pair) && !usedNumbers.contains(pair)) {
            usedNumbers.add(num);
            pairs.add(new Pair(num, pair));
        }
    }

    return pairs;
}

This implementation has another advantage: you don't need a Set<Pair>, it could be a List<Pair>, so you don't need the .equals and .hashCode methods in Pair.

The less code you have, the less complex is your solution. Some would say that managing complexity (keeping it down) should be the primary technical imperative of software construction.

Answer 3

I didn't check your algorithm, but I think the code could use some object-orientation!

You shouldn't have a main method in the class that holds your algorithm. Use a Program class, code your main there, and keep your PairsSummingToElement clean.

class Program{

    public static void main(String[] args) {
        PairsSummingToElement e = new PairsSummingToElement();
        int[] input = new int[] { 2, 5, 3, 7, 9, 8 };
        int sum = 11;
        e.findAllPairs(input, sum);
    }
}

Remove the main from your class, it doesn't belong there :)

The indentation is quite small, maybe it is this way because of how you posted your code here but I hope your production code has a better indentation. Finally, consider commenting your code, it will be easier to understand your algorithm for other programmers.

Answer 4

I see there are couple of really good suggestions which I like whole heartedly. Have a few more to add:

• Lets make methods like addToSet, reversePair as private. These methods should be leaked to the outside world. At the same time, the less your clients know the better.