Given an array of distinct numbers, how do we count the number of triplets with given sum?
For example let us consider the array {5, 2, 7, 8, 4, 3} and the sum is 14,
There are 3 triplets with the given sum
(2,5,7)
(2,4,8)
(3,4,7)
There are 3 triplets with the given sum
(2,5,7)
(2,4,8)
(3,4,7)
A brute-force algorithm will take O(n3) time. But this problem can also be solved based on 2 Sum problem. Here is the approach.
- Sort the array first.
- Fix the first element in the triplet, and search for a pair of elements whose sum is (Sum – Fixed element)
- Repeat the above step for all the elements
We are essentially searching for a pair of elements for each fixed element. So the time complexity of this solution would be O(n2).
One variation/follow-up of this problem could be to find out the number of triplets with sum less than or equal to the given value.
Considering the first example again, there are 8 triplets with sum less than or equal to 14.
2 3 4
2 3 5
2 3 7
2 3 8
2 4 5
2 4 7
3 4 5
3 4 7
2 3 5
2 3 7
2 3 8
2 4 5
2 4 7
3 4 5
3 4 7
The solution for this is similar to the first problem and uses the trick discussed in my previous post.
The code for both is given in the following Java program.