找出增加的三元组,使得和小于或等于k

Find increasing triplets such that sum is less than or equals to k

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)
This was voted up for deletion for low quality and I fixed it up. You mentioned you didn't know how to format your code, this can help you with that: stackoverflow.com/editing-help Also remember that link only answers to your own blog is a bit suspicious because it smells of self promotion. In your answer, always put a title explaining what you intend to do, how it works and what the result was even if it's clearly stated in the question because we want to know what your perspective is. Also if you can reduce indentation so that your output fits in the window, that would be cool.

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:

  1. b[k] = 7. At this time the treeSet is empty, so nothing happens, and 7 gets added to the treeSet.

  2. 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)

  3. 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.

Thanks a lot Ishamel. WIll it be possible to add an example. I also think that something is missing code .. Where are you adding elements in treeset ?
I add to the treeSet on the very last line. On the first iteration the treeSet is empty, so the loop will just naturally do nothing, the first element will be added, and the real work will start from the second iteration on k.
I added a small example. It is hard to find an example which hits all the corner cases, I would suggest to code it, add some prints into the code to see what it does, and run on some examples.

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.

@Ishamael Yep. But I have a feeling that it is actually not O(n^2) but that cost will be part of O(p) (reason being once you find a unfruitful j you stop). But too busy to prove that!
very good point, since the 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 is, making the complexity of your approach O(n log n + p), which is awesome.
And you don't even need BSTs, you only add linear number of times, so sorted arrays instead of trees would do just fine, and will simplify the solution.

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.

Waiting to hear back :)
Thanks for replying. Yes, I should have mentioned that array is not sorted.
I also wrongly wrote the question. I wanted to ask for d[i]+d[j]+d[k] <= t; Please suggest

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.

you are right, i'll try to fix it.. @Ishamael
Your complexity is wrong. Going from left to the found number has linear complexity, and you do it in two nested loops, so the complexity is O(n^3).
@Ishamael it's correct..read again, the sort is what makes it possible + my bound is output sensitive (there is a k in there if you look closely and the k could be O(n^3) :)
It is incorrect, because as you scan from the left side of the sorted array to the element found by binary search, you are not guaranteed that the elements you scan actually contribute to the answer. They might violate the condition that 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.
As an example, consider the array that has 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