Three sum problem using HashMap in Java

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.

Here is my code which addresses all the issues. One concern is the code looks a little muddy which I want to avoid in the production grade code. Any constructive feedback is appreciated.

Runtime: O(n2)

GitHub

public class ThreeSum {

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 int hashCode() {
return Objects.hash(triplets.get(0), triplets.get(1), triplets.get(2));
}

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

Triplet other = (Triplet) o;
return other.triplets.get(0) == this.triplets.get(0) &&
other.triplets.get(1) == this.triplets.get(1) &&
other.triplets.get(2) == this.triplets.get(2);
}

return false;
}

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

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 triplet
for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
int complement = targetSum - numbers[currentIndex];

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

if (currentIndex != indexes && currentIndex != indexes) {
int x = numbers[indexes], y = numbers[indexes];
}
}
}

return triplets;
}
}

• You are storing the integers of a Triplet as a List internally, yet you are not really taking advantage of the interface List's functionality. For example:

return Objects.hash(triplets.get(0), triplets.get(1), triplets.get(2));

Why not simply do this:

return triplets.hashCode();

Or, another example:

return other.triplets.get(0) == this.triplets.get(0) &&
other.triplets.get(1) == this.triplets.get(1) &&
other.triplets.get(2) == this.triplets.get(2);

This can be replaced by this:

return other.triplets.equals(this.triplets);

• There's an issue I didn't catch in the old question but which was already present there: Your code doesn't consider the possibility that the same sum is formed by more than one pair of numbers, because you are simply mapping integers to one pair of indices, and if you encounter a pair that adds up to a sum that is already stored in lookup, the old index pair gets overridden.

A way to overcome this problem could be to map the integers to a List<int[]>), but this would make things even more complicated, and I think the reason that this would get overly complicated is that you are, in fact, hard-coding a recursive process (first you create the pairs, then from the pairs you create the triplets etc.). You could instead try to write a method that accumulates all possible n-tuplets, with n being any arbitrary positive integer, through recursion, e.g. like this:

• If n is 1, then return an array/list of all integers
• If n is greater than 1, then iterate through the original array and, for every integer in it, combine this integer with all n-1-tuplets formed by the numbers that follow this integer in the array (taking only the following numbers and not the preceding numbers prevents duplicate tuplets that only differ in the order of the integers).

I imagine that this would be much easier to code than what you currently have (maybe this is also what you mean by your code being "muddy"), and also much more flexible. True, if it's just about pairs, then it might not be as fast as what you did here, but if it comes to tuplets of more than 2 numbers, I don't think there is much benefit of what you are trying to do here (although this is just a guess, I didn't actually benchmark it).

• great feedback. Are you referring to generate all 3 tuples which will result into 0(n3) unless I am missing the point. Mar 26 '18 at 18:58
• The issue you mentioned is not a problem. Even if the sum gets overridden there will be some other pair contributing for that. Lets take an example of input set as 6,6,9,3,12 and targetSum as 24. Here, 6+6=12 and 9+3=12, so only one pair will be saved in the lookup map. Yet that would not be a problem.Lets say (9,3) is saved in the map. But there is a complementary pair for (6,6) which is (6, 12) and that will ensure you will get the (6,6,12) eventually in the result. So the algorithm as is works fine and not prone to the issue you mentioned. Mar 26 '18 at 20:07
• @Exploring I have not fully thought this through, but for some reason, if you add 9 to your example input array, so that the input is 6,6,9,9,3,12, your code will not find the triplet (6,6,12), so apparently, the issue is a problem, although I have not thoroughly analyzed why exactly the addition of a 9 to the input array has this effect. Mar 26 '18 at 21:02
• @Exploring Well, what are debuggers for: In my example, the lookup table contains the following entries: 18=9+9, 21=9+12, 9=6+3, 12=9+3, 15=3+12. With neither 12=6+6 nor 18=12+6 in the lookup table, it's clear why the triplet (6,6,12) is not found. Mar 26 '18 at 21:11
• yeah - both the complementary pairs got overwritten and thus we lost the pair. Mar 26 '18 at 21:44

Your code is quite inefficient by storing all the sums of pairs into the hashmap.

The memory requirements grow exponentially (adding array entry n adds n more pairs, so it grows in a factorial manner).

You are better off by holding onto a pair only as long as you need it. This can be done by checking all possible additions to that pair at once and then throwing it away.

This is most easily done recursively. You have a set of numbers, and the next number you can either include in your set or not. Repeat this recursively.

Generally, for any given set of array values, you hold onto it only as long as you need it, to try combining it with other items from the array. Once you find a solution you save it. Once you've exhausted all possibilities with that set you throw it away.

public class Recurse {
static final int target = 24;
static final int sumCount = 3;
ArrayList<int[]> solutions = new ArrayList<int[]>();

public void sum(int arr[], int arrayIndex, int sum, int indicesSoFar[]) {
//you can either include the current value or not

//first we try skipping it
if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) { //only skip if there are enough numbers left
sum(arr, arrayIndex + 1, sum, indicesSoFar);
}
//now we try using it
int val = arr[arrayIndex];
int added = val + sum;
if(indicesSoFar.length + 1 == sumCount) {//if we use it, it is the last in the set
if(added == target) {// the sum matches, so it is a solution
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
}
} else if(added <= target) {//use it if we can (the sum is not too large).  This assumes all array values are positive, if negative values allowed, then remove the "if(added <= target)" condition
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
sum(arr, arrayIndex + 1, added, next);
}
}

public static void main(String args[]) {
new Recurse().sum(new int[] {12, 3, 4, 1, 6, 9}, 0, 0, new int);
}
}

That's all you need when you use the recursive approach. If you add code to print out the results as shown:

public static void main(String args[]) {
Recurse recurse = new Recurse();
int arr[] = new int[] {12, 3, 4, 1, 6, 9};
recurse.sum(arr, 0, 0, new int);
for(int solution[] : recurse.solutions) {
StringBuilder vals = new StringBuilder();
StringBuilder indices = new StringBuilder();
for(int index : solution) {
if(vals.length() > 0) {
indices.append(", ");
vals.append(" + ");
}
indices.append("arr[").append(index).append("]");
vals.append(arr[index]);
}
System.out.println("Solution: " + indices + "; " + vals);
}
}

Then it gives you:

Solution: arr, arr, arr 12 + 3 + 9

Now, according to your requirements you don't want multiple values used, but it's not clear to me if you are only talking about not using the same array element more than once (ie a[i] can appear just once for each i in each solution) or you are talking about using the same number more than once (ie the number x can appear only once in each solution), or you are talking about using the same set of added numbers more than once (the solution x,y,z can appear just once). If you want to handle the other cases, such as to prevent solutions with duplicate values then just check the existing solutions before adding another. Using a HashSet is ideal for this:

public class Recurse {
static final int target = 24;
static final int sumCount = 3;
ArrayList<int[]> solutions = new ArrayList<int[]>();
ArrayList<int[]> duplicates = new ArrayList<int[]>();
HashSet<ArrayList<Integer>> solutionSet = new HashSet<ArrayList<Integer>>();

public void sum(int arr[], int arrayIndex, int sum, int indicesSoFar[]) {
//you can either include the current value or not

//first we try skipping it
if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) { //only skip if there are enough numbers left
sum(arr, arrayIndex + 1, sum, indicesSoFar);
}
//now we try using it
int val = arr[arrayIndex];
int added = val + sum;
if(indicesSoFar.length + 1 == sumCount) {//if we use it, it is the last
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
ArrayList<Integer> solution = new ArrayList<Integer>();
for(int i : next) {
}
Collections.sort(solution);
if(!solutionSet.contains(solution)) {
} else {
}
}
} else if(added <= target) {//this assumes all array values are positive, if negative allowed, then no "if(added < target)" here
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
sum(arr, arrayIndex + 1, added, next);
}
}

public static void main2(String args[]) {
new Recurse().sum(new int[] {12, 3, 4, 1, 6, 9}, 0, 0, new int);
}

public static void main(String args[]) {
Recurse recurse = new Recurse();
int arr[] = new int[] {12, 3, 4, 1, 6, 3, 9};
recurse.sum(arr, 0, 0, new int);
for(int i = 0; i < 2; i++) {
String label = i == 0 ? "Solution: " : "Duplicate: ";
ArrayList<int[]> solutionList = i == 0 ? recurse.solutions : recurse.duplicates;
for(int solution[] : solutionList) {
StringBuilder vals = new StringBuilder();
StringBuilder indices = new StringBuilder();
for(int index : solution) {
if(vals.length() > 0) {
indices.append(", ");
vals.append(" + ");
}
indices.append("arr[").append(index).append("]");
vals.append(arr[index]);
}
System.out.println(label + indices + "; " + vals);
}
}
}
}

Which gives:

Solution: arr, arr, arr; 12 + 3 + 9
Duplicate: arr, arr, arr; 12 + 3 + 9
• Its utterly wrong to say grows in a factorial manner - its O(n2) :-) Apr 3 '18 at 18:51
• yes, you're right, got a little mixed up there, the number of permutations grows in factorial manner, the number of pairs is O(n2). Apr 3 '18 at 21:50