2
\$\begingroup\$

Given an array and a value, find all the triplets in the array whose sum is equal to the given value. For example, if the given array is {12, 3, 4, 1, 6, 9} and the given sum is 24, then this is one triplet (12, 3 and 9) which contributes to the total sum of 24.

Solution for given example:

6, 9, 9

6, 6, 12

3, 9, 12

The ordering of the numbers in the solution does not matter.

Duplicate triplet is not allowed.

A number is not allowed to be used multiple time.

Here is my code:

package kata.array;

import java.util.*;

public class ThreeSum {

  static class Triplet {
        int x, y, z;

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

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

        @Override
        public boolean equals(Object o) {
            if (o instanceof Triplet) {
                Set<Integer> numbers = new HashSet<>();
                numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));

                Triplet other = (Triplet) o;
                return numbers.containsAll(new ArrayList<>(Arrays.asList(other.x, other.y, other.z)));
            }

            return false;
        }
    }

    public static Set<Triplet> findTriplets(int numbers[], int targetSum) {
        Set<Triplet> triplets = new HashSet<>();

        // insert all pairs in the look up table
        Map<Integer, int[]> lookup = new HashMap<>();
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                int total = numbers[i] + numbers[j];
                lookup.put(total, new int[]{i, j});
            }
        }

        // look for the complement, if found viola! here you go with the matching triplet
        for (int number : numbers) {
            int complement = targetSum - number;

            if (lookup.containsKey(complement)) {
                int indexes[] = lookup.get(complement);
                int x = numbers[indexes[0]], y = numbers[indexes[1]];
                triplets.add(new Triplet(x, y, number));
            }
        }

        return triplets;
    }
}

To run this code:

public void findTriplets() throws Exception {
    int numbers[] = {12, 3, 4, 1, 6, 9};

    System.out.print(ThreeSum.findTriplets(numbers, 24));

    for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
        System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
    }

    // can handle duplicate?
    System.out.println("==============================");
    numbers = new int[] {12, 3, 4, 1, 6, 9, 9, 9, 9, 9};

    System.out.print(ThreeSum.findTriplets(numbers, 24));

    for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
        System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
    }
}

GitHub

\$\endgroup\$
8
  • \$\begingroup\$ this problem is quite similar to your last question. why don't you have a similar solution for both? \$\endgroup\$ Mar 24, 2018 at 21:40
  • 1
    \$\begingroup\$ @TimothyTruckle Is it a problem to submit different solutions for similiar problems for code review? Even if the problems were identical, I can't think of a reason not to try different approaches and having them all reviewed. I think it would rather be questionable to submit similar solutions in separate questions, because then, a review of one question is likely to applicable to the other question as well. \$\endgroup\$
    – Stingy
    Mar 25, 2018 at 11:04
  • \$\begingroup\$ @Stingy " Is it a problem to submit different solutions for similiar problems for code review?" of cause not. That was not my intention. \$\endgroup\$ Mar 25, 2018 at 11:59
  • \$\begingroup\$ @Stingy "Even if the problems were identical, I can't think of a reason not to try different approaches" Yes. But I doubt that you did in this case. At least nothing in you question supports that you intentionally choose a different approach. \$\endgroup\$ Mar 25, 2018 at 12:01
  • \$\begingroup\$ @Stingy "Even if the problems were identical, I can't think of a reason not to try different approaches" Also: successful programmers are able to find reusable solutions, that means approaches, that can be easily adopted to similar problems. \$\endgroup\$ Mar 25, 2018 at 12:11

3 Answers 3

1
\$\begingroup\$
  • Triplet.hashCode() and Triplet.equals(Object) are not compatible with each other. Triplet.hashCode() considers the order of the three integers, while Triplet.equals(Object) doesn't. Judging by the complexity of your method Triplet.equals(Object), I assume that you intend the order of the integers to be disregarded. A way to accomplish this would be to sort the integers in the method hashCode() before calculating the hash.

  • In fact, Triplet.equals(Object) is itself broken. Consider this: If we define Triplet a = new Triplet(1,2,3) and Triplet b = new Triplet(1,1,1), then a.equals(b) will return true, but b.equals(a) will return false.

  • Regardless of the above, you are creating unnecessary Lists in Triplet.equals(Object):

    numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));
    

    Here, the explicit creation of an ArrayList from the contents of the List returned by the invocation of Arrays.asList(T... a) is redundant – the following would suffice:

    numbers.addAll(Arrays.asList(x, y, z));
    

    The same applies to the process of converting the elements of other to a List. You could even bypass the creation of an intermediate List completely by using a stream:

    Set<Integer> numbers = Stream.of(x,y,z).collect(Collectors.toSet());
    

    But this is not going to help you anyway, because if you have two triplets like {1,1,2} and {1,2,2}, then Sets are useless for comparing the two triplets.

    The easiest way to go about it is probably, just like in the method hashCode(), to sort the integers from the triplets as a List and then compare the two Lists for equality. Actually, you could already sort the integer's in the Triplet's constructor, which would ensure that you only ever have to sort the three integers of a Triplet once. True, this does not preserve the order of the integers, but then, this is not really necessary for the purpose of this program either.

  • Your code fails in scenarios such as the following: If the input array is {5, -5, 7} and the target sum is 5, then your code will yield a non-existing triplet [5, -5, 5], because it counts the integer 5 twice.

\$\endgroup\$
4
  • \$\begingroup\$ good catch, good catch. Should I correct the implementation in the question? Or whats the SO policy regarding this? \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 12:32
  • \$\begingroup\$ @Exploring No, you should not alter the code in the question (see here). You can, however, open a new question with a new version of your code and, in that new question, link to this question. \$\endgroup\$
    – Stingy
    Mar 25, 2018 at 12:44
  • \$\begingroup\$ awesome, lets do that. I shall push a new version of this code. \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 12:46
  • \$\begingroup\$ still thinking the workaround for your last comment. One approach can be to save the original index in the map and then to validate that we are not re-using the same index value. \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 17:24
1
\$\begingroup\$

Arrays.asList(other.x, other.y, other.z) already returns a new list. There is no need to add the result to a new ArrayList you could just use

numbers.containsAll(Arrays.asList(other.x, other.y, other.z));

You creating some unnecessary objects that still need to be cleaned up by the garbage collector. e.g.: this could save you some memory. Instead of:

numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));

use

numbers.add(x);
numbers.add(y);
numbers.add(z);

Here you can save one lookup in the HashMap. Instead of:

if (lookup.containsKey(complement)) {
    int indexes[] = lookup.get(complement);
    ...

you can write:

int indexes[] = lookup.get(complement);
if (indexes != null) {
    ...
\$\endgroup\$
1
  • \$\begingroup\$ Good point regarding creating the unnecessary objects, good catch. Regarding the lookup.containsKey(complement) not too sure though - for me its a premature optimization. \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 12:23
0
\$\begingroup\$

Here are my 2 cents:

The reason why you came up with two different solutions is: Your mind is preset to procedural solutions an premature optimization.

A straight forward solution for the "sum of two" problem would be like this:

  1. build every possible pair
  2. remove duplicates
  3. calculate sum
  4. add to result if sum matches

The "sum of three" problem only differs in step 1. and step 3. (where step three could easily be derived to work with any number of elements).

So here is how I'd done that task:

sum of two

public class TwoSumProblemUsingBinarySearch {

    public static class Pair {

        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = Math.min(x, y);
            this.y = Math.max(x, 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 boolean hasSumOf(int target) {
            return target == x + y;
        }

    }

    public static Set<Pair> findAllParis(int input[], int target) {
        Set<Pair> pairs = createDistinctPairsFromInput(input);
        return removePairsNotMatchingTarget(target, pairs);
    }

    private static Set<Pair> createDistinctPairsFromInput(int[] input) {
        Set<Pair> pairs = new HashSet<>();
        for (int x : input) {
            for (int y : input) {
                pairs.add(new Pair(x, y));
            }
        }
        return pairs;
    }

    private static Set<Pair> removePairsNotMatchingTarget(int target, Set<Pair> pairs) {
        return pairs.stream().filter(p -> p.hasSumOf(target)).collect(Collectors.toSet());
    }
}

Yes, this solution might perform awfully for large input arrays but with the given example it is fast enough.

sum of three

What do we need to change to adopt the previous solution to the "sum of two" solution to the "sum of three" problem?

  • we need to change the ´Pair` class to handle 3 (or more) values
  • we need to add another foreach loop in the Pair factory method

so lets first change the Pair class:

public static class Pair {

    private final List<Integer> numbers =new ArrayList<>();

    public Pair(int... y) {
        for (int i : y) {
            numbers.add(i);
        }
        Collections.sort(numbers);
    }

    @Override
    public int hashCode() {
        return Objects.hash(numbers);
    }

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

    @Override
    public String toString() {
        return String.format("(%s)", numbers.stream()
                 .map(i -> i.toString())
                 .collect(Collectors.joining(", ")));
    }

    public boolean hasSumOf(int target) {
        return target == numbers.stream().mapToInt(i->i).sum();
    }

}

This still passes your test case for the "sum of two" problem.

And now we change the Pair creation method to adopt the new requirement:

private static Set<Pair> createDistinctPairsFromInput(int[] input) {
    Set<Pair> pairs = new HashSet<>();
    for (int x : input) {
        for (int y : input) {
            for (int z : input) {
                pairs.add(new Pair(x, y, z));
            }
        }
    }
    return pairs;
}

Now we have a similar solution for a similar problem. We could even go further and transform the factory method for the Pairs to be parameterized so that the same solution could be used for all "find combinations with matching sum" problems.

conclusion

My approach is totally focused on the problem. No optimization or "clever tricks" have been used. That allowed me to easily extend the first approach to a more general version to handle similar problems.

\$\endgroup\$
5
  • \$\begingroup\$ I found this answer way off the chart - appreciate the author understands he is not focusing on optimisation. Yes sacrificing and proposing O(n2) solution for two sum and O(n3) for 3-sum does not make any sense and not acceptable. But appreciate the alternative view. \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 13:17
  • \$\begingroup\$ This code has serious bug while generating the distinct pairs for three sum as it is going to take each number multiple times. For example, if the input set is {1, 2, 3} it will make tuples of (1,1,1) which is not a intended one. \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 13:36
  • \$\begingroup\$ @Exploring "This code has serious bug while generating the distinct pairs for three sum as it is going to take each number multiple times." This is not a bug, and it is not "serious". It is just not optimized. \$\endgroup\$ Mar 25, 2018 at 13:38
  • \$\begingroup\$ This is a serious bug and completely broken, please have a look for the input case (1,2,3), it is creating useless pairs like (1,1,1), (2,2,2), (3,3,3) which is not correct. \$\endgroup\$
    – Exploring
    Mar 25, 2018 at 13:40
  • \$\begingroup\$ @Exploring They would be "incorrect" if they would make it into the result. And the mission statement does not tell that a number cannot be "paired" or "grouped" with itself. \$\endgroup\$ Mar 25, 2018 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.