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

Question

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.

Answer 1

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.

Answer 2

I think it can be solved in O(n^2logn) time, using TreeMap or Sorted Map concept. I have tried to implement the same in Java, but the concept remains the same.

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        int arr[]={1,2,3,3,4,4,9,10,11,342,43};
        int n=arr.length,t=98,cnt=0;
        Arrays.sort(arr);
        for(int k=2;k<n;k++)
        {
            TreeMap<Integer,Integer> ts1=new TreeMap<>();
            for(int j=0;j<k;j++)
            {
                if(arr[j]==arr[k])
                break;
                int i=Math.min(t-arr[k]-arr[j],arr[j]); //try to get the number of elements less than arr[j] and target-arr[k]-arr[j]
                cnt+=(ts1.lowerKey(i)==null?0:ts1.get(ts1.lowerKey(i)));
                
                if(ts1.containsKey(arr[j]))
                ts1.put(arr[j],ts1.get(arr[j])+1);
                else
                {
                    Integer val=ts1.lowerKey(arr[j]);
                    ts1.put(arr[j],1+(val==null?0:ts1.get(val)));
                }
            }
        }
        System.out.println(cnt);
    }
}

Let me know if it works for you.

Answer 3

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)

Answer 4

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.