Here’s the problem statement:
Given an array of unique integers, find all quadruplets of distinct integers (in any order) that add up to a given target sum.
For example:
The array: 10, 20, 30, 40, 1, 2
Target sum: 91
Output: [[20, 30, 40, 1]]
Let’s dive into the solution: Let’s try to build the solution using the insights we gained in the Pair Sum problem.
A small recap:
In the Pair Sum problem’s Approach 3 we maintained a set of the integers that we had already seen. These integers represented intermediate sums and every time we saw a new integer (another possible intermediate sum), we checked if it could be added up with anything already present in our set to get the target sum.
We’re now gonna reduce the Quadruplet Sum problem to the Pair Sum problem.
The Idea:
1. We’ll try to find a pair of intermediate sums that add up to the given target sum. Here, each intermediate sum will itself be the summed up value of a pair of integers in the given array. For the given example we’ll find two intermediate sums P and Q that sum up to 91, where P = a + b and Q = c + d and a, b, c, d are integers in the given array.
2. To archive the intermediate sum we’ve visited, we’re gonna maintain a HashMap of <Integer, List<int[]>> to store a mapping of intermediate sum to list of pair of integers that sum up to the intermediate sum. Note that we intend to use lists as the values in the HashMap because for each intermediate sum there maybe >1 pairs of integers in the array that add up to it, i.e., there maybe the case where a1+b1 = Q and a2+b2 = Q, we’d then have quadruplets a1+b1+c+d = target and a2+b2+c+d = target as part of the solution.
The Implementation:
- Generating pairs and then quadruplets:
- Generate pairs of intermediate sums using doubly nested loops (i, j) and set P = [arr[i]+arr[j]]
- Lookup the HashMap to see if it contains Q(=target-P) as a key.
- If it does (say with value: [[x,y]), then we’ve found a quadruplet: [arr[i], arr[j], x, y]
- Archiving (i.e. Adding to the HashMap) the intermediate sums:
If we were to archive every pair as we got to it, we would end up with many instances of the same quadruplet differing in order.
For instance, if we archived:
[10,20], [10,30], [10,40], [10, 1], [10, 2],
[20,30], [20,40], [20,1] [20,2],
[30,40], [30,1], [30,2],
[40,1], [40,2],
[1,2] as we visited them, then,
at pair P=[30,40] we’d create quadruplet: [P=[30, 40], Q=[20, 1]]
and at P=[30,1] we’d create [P=[30, 1], Q=[20, 40]]
and at P=[40,1] we’d create [P=[40,1], Q=[20,30]]
Let’s analyse what really is the problem here:
When P=[30,40], then of the two values in Q=[20,1], although one of them i.e. ’20’ lies behind ’30’ (the ith index) and will therefore never appear again as part of another P BUT ‘1’ lies ahead of the current ith index, so in the future, ‘1’ will appear in P.
This does happen at P=[30,1] where we have Q=[20,40] and again though ’20’ lies before the current ith index and will therefore never appear again as part of another P BUT 40 lies after it so again in the future 40 will appear in P.
This does happen at P=[40, 1] where we have Q = [20, 30] where now ’20’ and ’30’ both lie before the current ith index and will therefore never appear again as part of another P.
So, if we can ensure that that the two array values that make up Q will not be a part of any P, then we’ve remedied the problem.
To do so, at every array[i], we create Qs=(array[i]+array[j2]) such that j2 goes from {0 to (i-1)} i.e. j2 is every element before i. We’ll place only such Qs in our HashMap. This way by archiving the intermediate sums backwards never will a value that is a part of some Q become a part of some P in the future.
This way we’ll archive:
[20 10],
[30 10], [30 20],
[40 10], [40 20], [40 30],
[1 10], [1 20], [1 30], [1 40],
[2 10], [2 20], [2 30], [2 40], [2 1]
Now, at P=[30,40] we won’t have [20, 1]
and at P=[30,1] we won’t have [20, 40]
while at P=[40,1] we’ll have [30,20] so we’ll create [40, 1, 30, 20].
Time Complexity: Avg. case: O(n2) since there are doubly nested loops (i, j) to generate all pairs and (i, j2) to archive intermediate sums.
Space Complexity: O(n2) – since we’re storing the HashMap that could have n2 keys for the different intermediate sums (since n2 number of pairs an be generated by using n numbers)
Here’s the code for this solution java:
public List<int[]> quadSum(int[] array, int target) {
List<int[]> ans = new ArrayList<int[]>();
int sum = 0; List<int[]> temp;
HashMap<Integer, List<int[]>> map = new HashMap<>();
for(int i = 0;i<array.length;i++) {
for(int j = i+1;j<array.length;j++) {
sum = array[i] + array[j];
if(map.containsKey(target-sum)) {
for(int[] values: map.get(target-sum)) { //for every pair in the list of values
ans.add(new int[]{array[i], array[j], values[0], values[1]});
}
}
}
for(int j2 = i-1;j2>=0;j2--) {
sum = array[i] + array[j2];
temp = map.getOrDefault(sum, new ArrayList<int[]>());
temp.add(new int[]{array[i], array[j2]});
map.put(sum, temp);
}
}
return ans;
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding!
The Code Scribbbler 