2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question after answers have been submitted, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Mar 21 '18 at 22:22
2
\$\begingroup\$
  • 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;
    }
    
\$\endgroup\$
  • \$\begingroup\$ I actually updated the equals in the GitHub code but forgot to paste back the code sample. Good catch - appreciate it. \$\endgroup\$ – Exploring Mar 21 '18 at 22:18
0
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ But in my proposed code, pastNumbers is a set of the numbers that have already been visited … (except the numbers whose complement has been visited before them) \$\endgroup\$ – Stingy Mar 21 '18 at 21:55
  • \$\begingroup\$ @Stingy You're right, sorry, I misread. I'll edit that part of my answer. \$\endgroup\$ – David Moles Mar 21 '18 at 22:10
  • \$\begingroup\$ @DavidMoles appreciate your feedback - but its probably also depends on the taste. I actually find remainingSum better as it clearly describes what we are looking for i.e. if the remainingSum is there, viola, we got our pair. Also sure naming it as map does not make sense, but not so sure about expected name either. On the other hand, I think overall sting's code rocks. \$\endgroup\$ – Exploring Mar 21 '18 at 23:16
  • \$\begingroup\$ @Exploring It's Code Review Stack Exchange. ¯\_(ツ)_/¯ I agree that expected is still less than obvious, but that's partly a factor of the algorithm. If you want to use Stingy's algorithm, I'd call it visited. The remainingSum name on the other hand is actively misleading — it's neither a remainder, nor a sum. I wouldn't let that go into production at my day job, and I don't think anyone on my team would either. But it's your code. \$\endgroup\$ – David Moles Mar 21 '18 at 23:40
  • \$\begingroup\$ @DavidMoles yeah - it depends on the view, so lets not get over opinionated :-). \$\endgroup\$ – Exploring Mar 22 '18 at 15:52
0
\$\begingroup\$

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;
    }
\$\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.