Return all pairs from a list of integers that contributes to a given sum

Question

Given a list of integers return all the pairs that makes up to a given target sum.

input: {2, 7, 11, 15, -2} target sum: 9

This should return all the pairs i.e {-2,11} and {7,2}.

If there are duplicates that form the same pair, they should not be returned.

Here is the code for this problem - would be great to know how this can be refactored for improvement.

   public class TwoSum {
    static class Pair {
        int x, y;

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

        @Override
        public boolean equals(Object o) {
            if (o == null) {
                return false;
            }

            if (o instanceof Pair) {
                Pair other = (Pair) o;
                if (other.x == this.x && other.y == this.y) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public String toString() {
            return new StringBuilder().append("{").append(this.x).append(",").append(this.y).append("}").toString();
        }
    }

    public static Set<Pair> findPairs(int inputs[], int targetSum) {
        Set<Pair> results = new HashSet<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int number : inputs) {
            int remainingSum = targetSum - number;

            if (map.containsKey(number)) {
                results.add(new Pair(number, map.get(number)));
            } else {
                map.put(remainingSum, number);
            }
        }
        return results;
    }

To invoke this code:

System.out.println(TwoSum.findPairs(new int[]{2, 7, 11, 15, -2}, 9));

This would print:

[{-2,11}, {7,2}]

Code here:

https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/TwoSum.java

Answer 1

• I see that you are overriding Object.equals(Object) without overriding Object.hashCode(). By doing this, you violate the contract of Object.hashCode() (see the last paragraph in the description of Object.equals(Object)). In fact, the HashSet<Pair> created in your findPairs method might not operate properly due to this.
• Since the values of x and y of a Pair instance never change, you could make x and y final, thereby making Pair an immutable class and preventing accidental tampering with the values of x and y.
• I don't know if you've considered this, but your code would treat {2,3} and {3,2} as two distinct pairs. Due to how the findPairs method works, it doesn't matter, since it will never create two pairs that only differ in the order of the two numbers, but I thought I'd point it out in case you were not aware of that.
• The null check in Pair.equals(Object) is redundant, since null instanceof X, with X being the name of class, will always return false.

• if (o instanceof Pair) {
      Pair other = (Pair) o;
      if (other.x == this.x && other.y == this.y) {
          return true;
      }
  }
  return false;
  

  can be written more concise as:

  if (o instanceof Pair) {
      Pair other = (Pair) o;
      return other.x == this.x && other.y == this.y;
  }
  return false;
  

• new StringBuilder().append("{")
  

  can also be shortened:

  new StringBuilder("{")
  

• You don't actually need a Map<Integer, Integer> in findPairs. The mapping of integers to their complement serves no purpose, because the complement of an integer can be simply calculated by subtracting it from the target sum. A Set<Integer> would suffice, since you just use the map to determine whether the complement of a number has already appeared in the sequence of numbers. So findPairs can be re-written as:

  public static Set<Pair> findPairs(int inputs[], int targetSum) {
      Set<Pair> results = new HashSet<>();
      Set<Integer> pastNumbers = new HashSet<>();
  
      for (int number : inputs) {
          int remainingSum = targetSum - number;
  
          if (pastNumbers.contains(remainingSum)) {
              results.add(new Pair(number, remainingSum));
          } else {
              pastNumbers.add(number);
          }
      }
      return results;
  }
  

Answer 2

As Stingy says your Pair should make x and y final and override hashCode(). Also, the StringBuilder in toString() is overkill -- it's hard to read and doesn't gain you anything in performance over simple concatenation (the compiler will replace simple concatenation with StringBuilder anyway). In this case I might even use String.format. (If you start with simple concatenation, your IDE will probably offer a quick-fix.)

When you're iterating over a plural, convention is for the loop variable to be the singular. So inputs 🡒 input, not number.

Right now remainingSum is only used in the else case, which suggests it should be inside the else block -- but read on:

It's not at all clear what the map is for; consider a more meaningful variable name than map. (In fact it's so unclear it's not even obvious at first glance whether the code is correct. You should almost never name a map map, a set set, etc.)

Stingy is probably right that you don't even really want/need a map, just a set, which (if you're going to use it the way you're using the map) I would call something like expected. Also, remainingSum is not a sum, and should be something like complement.

That gets us as far as:

Set<Pair> results = new HashSet<>();
Set<Integer> expected = new HashSet<>();

for (int input : inputs) {
  int complement = targetSum - input;

  if (expected.contains(input)) {
    results.add(new Pair(input, complement));
  } else {
    expected.add(complement);
  }
}
return results;

-- so we now have a reason for complement (formerly remainingSum) to be outside the if/else block.

Personally, I think the algorithm is still a little muddy and hard to explain, and it would be more clear if, as in Stingy's version, you stored the visited numbers (input, formerly number) instead of the numbers-that-would-indicate-a-success-if-we-should-visit-them-later (complement, formerly remainingSum).

Answer 3

Addressing the comments here is the answer:

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

static class Pair {
        final int x, y;

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

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

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

        @Override
        public String toString() {
            return new StringBuilder("{").append(this.x).append(",").append(this.y).append("}").toString();
        }
    }

    public static Set<Pair> findPairs(int inputs[], int targetSum) {
        Set<Pair> results = new HashSet<>();
        Set<Integer> visited = new HashSet<>();

        for (int number : inputs) {
            int complement = targetSum - number;

            if (visited.contains(number)) {
                results.add(new Pair(number, complement));
            } else {

                visited.add(complement);
            }
        }
        return results;
    }