Find triplets in an array whose sum is some integer X

Question

Given a sorted array[1..n] where each element ranging from 1 to 2n. Is there a way to find triplet whose sum is given integer x. I know O(n^2) solution. Is there any algorithm better than n^2 ones.

Answer 1

It is possible to achieve an O(n log n) time complexity using that fact the maximum value of each element is O(n).

1. For each 1 <= y <= 4 * n, let's find the number of pairs of elements that sum up to y. We can create a polynomial of 2 * n power, where the i-th coefficient of this polynomial is the number of occurrences of the number i in the given array. Now we can find the square(I'll call it s) of this polynomial in O(n log n) time using Fourier's Fast Transform. The i-th coefficient of s is exactly the number of pairs of elements that sum up to i.

2. Now we can iterate over the given array. Let's assume that the current element is a. Then we just need to check the number of pairs that sum up to X - a. We have already done it in the step 1).

If all triplets must consist of different elements, we need to subtract the number of such triplets that sum up to X but contain duplicates. We can do it in O(n log n) time, too(for triplets that consist of three equal elements, we just need to subtract the number of occurrences of X / 3 in the given array. For triplets with one duplicate, we can just iterate over the element that is repeated twice(a) and subtract the number of occurrences of X - 2 * a).

If we need to find a triplet itself, not just count them, we can do the following:

1. Count the number of triplets and pairs as suggested above.

2. Find such an element that there is a pair that sums up to X with it.

3. Find two elements that sum up to the desired sum of this pair.

All these steps can be accomplished in linear time(using the fact that all sums are O(n)).

Answer 2

Your problem is apparently the non-zero sum variant of the 3SUM problem.

Because you know the possible range of the integers beforehand, you can achieve lower bounds than the general case, according to the second paragraph of the article:

When the elements are integers in the range [-N, ..., N], 3SUM can be solved in O(n + N log N) time by representing the input set S as a bit vector, computing the set S + S of all pairwise sums as a discrete convolution using the Fast Fourier transform, and finally comparing this set to -S.

In your case, you would have to pre-process the array by subtracting n + X/3 before running the algorithm.

One thing to note is that the algorithm assumes you're working with a set of numbers, and I'm not sure what (if any) implications there may be on running time if your array may include duplicates.