The easier or more popular version of this problem is to find triplets with a given sum. But this one puts an extra condition. Find all triplets in the unsorted array such that
d[i]+d[j]+d[k] <= t; & d[i]<d[j]<d[k] where i<j<k
THIS is the solution to the the first part of the problem. But can someone please suggest how can we extend it to include second condition as well. Only way I can think of is to do a custom data structure while sorting to store original element index as well with the number. And then checking if indexes are in order for every triplet returned by the algorithm mentioned in the included link.
With condition, where i<j<k
half of your cube is not eligible, so you can eliminate what's not required
for (int k = 0; k < N, k++)
{
for (int j = 0; j < k, k++)
{
if (d[j] < d[k]) continue;
for (int i = 0; i < j, i++)
{
if (d[k] < d[j]) continue;
if (d[i]+d[j]+d[k] <= t)
{
//valid result
}
}
}
}
Find increasing triplets such that sum is less than or equals to k:
# include <stdio.h>
void find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
for (int i = 0; i < arr_size-2; i++){
for (int j = i+1; j < arr_size-1; j++){
for (int k = j+1; k < arr_size; k++){
if (A[i] + A[j] + A[k] <= sum)
printf("Triplet is %d, %d, %d\n", A[i], A[j], A[k]);
}
}
}
}
int main()
{
int A[] = {1, 2, 3, 4, 6};
int sum = 8;
int arr_size = sizeof(A)/sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
Output :
Execution :
arr_size = 5
Step:1 i=0 and i<3 (arr_size-2)
j=1 and j<4 (arr_size-1)
k=2 and k<5 (arr_size)
A[0]+A[1]+A[2]<=sum --> 1+2+3 <=8 --> 6<=8 ( true )
k=3 and k<5
A[0]+A[1]+A[3]<=sum --> 1+2+4 <=8 --> 7<=8 ( true )
k=4 and k<5
A[0]+A[1]+A[4]<=sum --> 1+2+6 <=8 --> 9<=8 ( false )
j=2 and j<4
k=3 and k<5
A[0]+A[2]+A[3]<=sum --> 1+3+4 <=8 --> 8<=8 ( true )
k=4 and k<5
A[0]+A[2]+A[4]<=sum --> 1+3+6 <=8 --> 10<=8 ( false )
j=3 and j<4
k=4 and k<5
A[0]+A[3]+A[4]<=sum --> 1+4+6 <=8 --> 11<=8 ( false )
j=4 and j<4 (false)
Step:2 i=1 and i<3
j=2 and j<4
k=3 and k<5
A[1]+A[2]+A[3]<=sum --> 2+3+4 <=8 --> 9<=8 ( false )
k=4 and k<5
A[1]+A[2]+A[4]<=sum --> 2+3+6 <=8 --> 11<=8 ( false )
j=3 and j<4
k=4 and k<5
A[1]+A[3]+A[4]<=sum --> 2+4+6 <=8 --> 12<=8 ( false )
j=4 and j<4 (false)
Step:3 i=2 and i<3
j=3 and j<4
k=4 and k<5
A[2]+A[3]+A[4]<=sum --> 3+4+6 <=8 --> 13<=8 ( false )
j=4 and j<4 (false)
Step:4 i=3 and i<3 (false)
First of all, it is worth pointing out, that the worst case complexity cannot be better than O(n^3)
, because in the worst case there are O(n^3)
triplets, and obviously you need at least constant time per triplet, to store/print it. And there's a very simple and obvious O(n^3)
algorithm.
That being said, here's how you can do it with a complexity O(n^2 log n + k)
, where k
is the size of the answer. (While @saadtaame claims to have the same complexity, he has an issue in his estimate, see comments below his answer).
First of all, let's fix one element, say a[i]
. Now let's create a new array b
consisting of all the elements from a
, that both have index greater than i
and a value greater than a[i]
. Now the problem reduces to finding two indexes j
and k
in b
, such that j < k
and b[j] < b[k]
.
To do that, we can use some kind of a sorted set, like a TreeSet
in Java. We will iterate over all possible values of k
, maintaining all the elements with indexes less than k
in the TreeSet
. Since the TreeSet
contains only the elements with indexes less than k
(because of the way we build it), and greater than i
(because b
only contained such elements), and is sorted, then every element q
in that TreeSet
that has a value smaller than b[k]
forms an answer triple (a[i], q, b[k])
. Here's a pseudocode:
for i from 0 to size(a):
b = empty array
for j from i + 1 to size(a):
if a[j] > a[i]:
add a[j] to b
treeSet = new TreeSet
for k from 0 to size(b):
for each element 'e' in the treeSet in sorted order: // (1)
if e >= b[k] or a[i] + e + b[k] > t:
break
add (a[i], e, b[k]) to the answer // (2)
add b[k] to the treeSet // (3)
Here if number of elements we return is less than O(n^2 log n)
, then the complexity of the algorithm will be O(n^2 log n)
. The reason is that the line (2)
is executed precisely k
times, and therefore can be ignored (and iterating over a treeSet has amortized linear time in number of elements), while the rest of the inner loop: initializing the iterator at (1)
and adding an element to the treeSet
at (3)
are both at most O(log n)
operations.
EDIT: here's a small example. Let's say the array is a = [5, 3, 7, 9, 8, 1]
and t = 20
. Then i
first points at 5
, we put all the elements that are to the right from 5
and bigger to b
, so b = [7, 9, 8]
. Then k
will do three iterations:
b[k] = 7
. At this time the treeSet is empty, so nothing happens, and 7
gets added to the treeSet.
b[k] = 9
. At this time the treeSet has element 7. It is smaller than 9, but the sum 5 + 7 + 9 > 20
, so we break from the iteration over the treeSet. We put 9
to the treeSet, to the set now contains (7, 9)
b[k] = 8
. We iterate over the treeSet. For element 7 both conditions are satisfied (7 < 8 and 5 + 7 + 8 <= 20
), so (5, 7, 8)
is added to the answer. For element 9 the element is bigger than b[k]
, so we break.
Then the loop over k
is over.
Then we move i
one element to the right. Content of b
will be exactly the same, and the three steps above will be almost the same, except that during the second step the answer will be small enough, so we will yield (3, 7, 9)
and (3, 7, 8)
.
Then as we move to the next i
, when a[i] = 7
, array b
will only contain two elements, [9, 8]
, and no answer will be produced.
I would recommend coding it in Java with some debug output, and playing with it for a bit to understand it better.
k
.I think you can do slightly better than O(n^2 log n + k).
Assume you are at position i. All the elements up to i (1...i) are stored in one BST, and all the elements after i (1+1...n) are stored in second BST.
In the first tree, find the smallest element A[j] such that A[j]
Now, in the second tree find largest element A[k] such that A[k] < k-A[i]-A[j]. If A[k]<=A[i] stop. Otherwise, print A[j],A[i],A[k], and set k = prev(A[k]) in the second tree. Loop around until A[k]<=A[i].
In the middle of all this, make an additional comparison. Let A[j1] = next(A[j]) (i.e. A[j1] is the next element in the sorted sequence). If for a k if it also follows conditions A[j1]+A[i]+A[k] <=t, note down such largest k. And in the next iteration, instead of binary searching use this k directly.
Initially start with i=2, firstTree={A[1]}, secondTree = {A[3]..A[n]}. And whenever you are increasing A[i], add A[i] to the firstTree and remove A[i+1] from second tree.
Overall time complexity: O(n^2+n*log(n)) + O(p) = O(n^2+p) where p is the number of total results.
Algorithm:
Initialization: firstTree={A[1]}, secondTree = {A[3]..A[n]}
For i = 2:(n-1) do:
j = getFirst(firstTree)
firstIter = true;
while(true)
if A[j]>=A[i] or A[j]+A[i]>t break
if firstIter:
k = binSearch(secondTree, t - A[i] -A[j])
firstIter=false
else
if bestk<0:
break;
k = bestk
bestk = -1
jnext = nextElement(firstTree, A[j]);
while (A[k]>A[i]):
print (A[j], A[i], A[k])
if bestk<0 and A[i]+A[jnext]+A[k] < t:
bestk = k;
k = prevElement(secondTree, A[k])
Add(firstTree, A[i])
Remove(secondTree, A[i+1])
Note that binSearch is called only once per i, and for one i nextElement goes through the tree exactly once (complexity O(n)). Inner while loop is called exactly once. So overall complexity is O(n^2 + nlogn + p) where p is the number of outputs.
EDIT: Since if we find a unfruitful j (i.e. no solution for j), we stop. I think this cost is incorporated in O(p) itself. So the final complexity is O(nlogn + p). Sorry, I don't have time to provide a detailed proof.
print
will not be executed more than p
times, we just need to prove, that number of iterations of while (true)
that do not call print is constant. And indeed, if on one of the iterations of while (true)
you don't call to print, you also did not assign bestk, which means that on the next iteration of while(true)
you will break. Thus while (true)
will do O(p + i)
iterations combined across all i
s, making the complexity of your approach O(n log n + p)
, which is awesome.Haha it's nice to see my blog referred here. However the post you linked solves d[i]+d[j]+d[k] < t
I think you should clearly ask if your array is sorted, then your problem is a slight extension of How to find pairs that equal to a specific sum in an array
So for your case (with assumption that array is sorted), you just have to make sure i, j, k are always in increasing order.
So a classic day-night approach (i.e. with j, k moving towards each other) considering N elements and a target T, you could try:
for (int i = 0; i < N, i++) {
int j = i;
int k = N-1;
while (j < k) {
int currSum = i+j+k;
if (currSum < T) { // increase sum
j++;
}
else if (currSum > T) { // decrease sum
k--;
}
else {
System.out.println("Found triple: " + i + ", " + j + ", " + k);
j++;
}
}
}
//i, j, k are guaranteed to be in increasing order.
If the array is not sorted, you could just do an optimized brute-force. So find all i, j such that d[i] < d[j] and i < j. Then on each of these pairs try to find a k, after j.
I think n^2*logn can be achieved in this case.
What we have to do is to sort using quick sort the numbers first so it will avoid extra loop and by default i < j < k.
My logic is d[i] + d[j] + d[k] <= t , so d[k] <= t - d[i] -d[j] so first loop will run 1 to n, second runs from i + 1 to n and for the 3rd we will do binary search of (t - d[i] -d[j]) and compare for d[i] < d[j] < d[k] to avoid duplicate. So by doing this we can get complexity of nlogn(sorting) + (n^2*logn) for find the sum.
So my call is:
Arrays.sort(d);
for (int i = 0; i < d.length; i++) {
for (int j = i + 1; j < d.length; j++) {
int firstNumber = d[i];
int secondNumber = d[j];
int temp = t - firstNumber - secondNumber;
if ((firstNumber < secondNumber) && (secondNumber < temp)) {
int index = Arrays.binarySearch(d, temp);
if (index >= 0) {
......
}
}
}
}
}
If you fix i and j, you'll have to find a number in the array that is less than or equal to t - d[i] - d[j]
. Store a second version of you array in which every element also stores it's index. Sort this array in increasing order.
Now, for all pairs i, j
with i < j
(this is just two nested for loops) you binary search for t - d[i] - d[j]
; if such a number exists you go over all number from the left up to this number and check that their indices are greater than j, if so you add to output. Complexity is O(n*n*lg n + k)
where k is the number of outputs that satisfy the condition.
EDIT: OP's first post was =
now he changed to <=
. I updated my answer.
k
in there if you look closely and the k
could be O(n^3)
:)a[i] < a[j] < a[k]
. The array is sorted by the value, but not by the index. So you after every binary search you might be doing linear work, while k
is very small, leading to O(n^3)
complexity, while k
is negligibly small.n / 3
twos followed by n / 3
zeros followed by n / 3
threes, and t
being very large. There's no answer in this array, so k
is zero, but for every i, j
such that a[i] = 2, a[j] = 3
(and there's O(n^2)
such pairs) your binary search will return a position in the sorted array after all the zeros, and you will have to scan all O(n)
zeros, and reject all of them, leading to an O(n^3)
complexity, while k = 0