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

Conditions:

  • 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 times.

A similar question was asked here, though it was HashMap-based.

Github

public class ThreeSumUsingBinarySearch {

     static class Triplet {
        final List<Integer> triplets;

        public Triplet(int x, int y, int z) {
            triplets = Arrays.asList(x, y, z);
            Collections.sort(triplets);
        }

        @Override
        public String toString() {
            return String.format("(%d,%d,%d)", triplets.get(0), triplets.get(1), triplets.get(2));
        }

        @Override
        public int hashCode() {
            return triplets.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Triplet) {

                Triplet other = (Triplet) o;
                return other.triplets.equals(this.triplets);
            }

            return false;
        }
    }

    public static Set<Triplet> findTriplets(int array[], int targetSum) {

        int[] numbers = Arrays.copyOf(array, array.length);
        Set<Triplet> triplets = new HashSet<>();

        Arrays.sort(numbers);

        for (int i = 0; i < array.length; i++) {
            int complement = targetSum - numbers[i];

            for (int low = i + 1, high = numbers.length - 1; low < high; ) {
                int total = numbers[low] + numbers[high];

                if (total < complement) {
                    low++;
                } else if (total > complement) {
                    high--;
                } else {
                    // found the match
                    triplets.add(new Triplet(numbers[i], numbers[low], numbers[high]));
                    low++;
                    high--;
                }
            }
        }

        return triplets;
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Just a small note as I have just noticed the "interview-questions" tag: if I were the interviewer, the most convincing solution for me would be to know that there's a library "apache-commons-math3" which contains CombinatoricsUtils that readily gives you a "choose k from n"-iterator. Using this iterator to create the index lookups, the whole thing basically becomes a one-liner. The best (professional) code is normally the one, that you do not need to write and maintain. ;-) \$\endgroup\$
    – mtj
    Mar 27 '18 at 11:54
  • \$\begingroup\$ @mtj thats a good point - however, in an interview setting solving them optimally is even more important as that clearly illustrates an engineers problem solving ability and critical thinking. \$\endgroup\$
    – Exploring
    Mar 27 '18 at 15:02
  • \$\begingroup\$ You state that "A number is not allowed to be used multiple times" yet your solutions show numbers being used twice \$\endgroup\$ Jul 4 '18 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.