Is there any way to reduce number of operations for finding and returning the number of triplets sum in array which is equals to any integer X

Question

The program is meant to find and return the number of triplets sum in the array/list which is equal to any integer value X.

triplets = (any three elements in array list)

The array can be in any order

Say, array size =7

Sample input : {1, 2, 3, 4, 5, 6, 7}

X = 12

Sample Output : 5

by reducing operations, I mean to reduce time complexity. As I wrote this code :

public static int tripletSum(int[] arr, int num) {
         int count = 0;
        
        for(int i = 0; i<arr.length; i++){
            
             for(int j = i+1; j<arr.length; j++){
                
                 for (int k = j+1; k<arr.length; k++){
                    
                    if ((arr[i] + arr[j] + arr[k])==num){
                        count++;
                    }
                }
            }
        }
        
         return count;
    }
 }

I get O(n^3) time complexity using this code and Time limit Exceeded error with this. Any way to reduce it to O(n^2) ?

https://stackoverflow.com/questions/17061686/find-all-possible-sublists-of-a-list — PM 77-1, Jul 29 '22 at 18:11
By sorting the list, you can at least reduce it to n^2 log n by binary searching for (num - a[i] - a[j]). — Louis Wasserman, Jul 29 '22 at 18:23
@LouisWasserman It will throw an error for any case greater than n^2 — Zeeshan, Jul 29 '22 at 18:34
At each iteration of the first two loops, check if the sum so far is already > X. If yes, then `continue` (to skip the next nested loop). For example, if arr[i] > x, then `continue`. — Andrew S, Jul 29 '22 at 18:34

score 2 · Accepted Answer · answered Jul 29 '22 at 18:34

Sorting is O(n log n), so if we're looking to reduce the complexity to O(n²), then sort the input so we can take advantage of the order.

Then, for all the elements except for the last 2^*, assume that that first element is part of the sum. Compute the target (12 here) minus the first element, call it sum. Maintain two indices, j and k, initialized to the next element and the last element. If the sum of the elements at j and k equals sum, count it. If we have too much, decrement k, else increment j. When j and k meet, you can move on to the next element and restart j and k.

[1, 2, 3, 4, 5, 6, 7]
 i  j ->        <- k

Here's the coded algorithm:

public static int numTripletsSum(int[] input, int target) {
    if (input == null || input.length < 3)
        return 0;
    Arrays.sort(input);
    int count = 0;
    for (int i = 0; i < input.length - 2; i++) {
        int sum = target - input[i];
        int j = i + 1, k = input.length - 1;
        while (j < k) {
            int diff = input[j] + input[k] - sum;
            if (diff == 0) {
                count++;
                //System.out.println("(" + input[i] + ", " + input[j] + ", " + input[k] + ")");
            }
            if (diff > 0) {
                k--;
            } else {
                j++;
            }
        }
    }
    return count;
}

This is two nested loops, O(n²), after an O(n log n) sort, so the algorithm is O(n²). For your input above, I get 5.

* _{Except for the last 2? You can't get a triplet from the second to last element on.}

Is there any way to reduce number of operations for finding and returning the number of triplets sum in array which is equals to any integer X

1 Answers1