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) ?

CodePudding user response：

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