Issue
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) ?
Solution
Sorting is O(n log n), so if we're looking to reduce the complexity to O(n2), 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(n2), after an O(n log n) sort, so the algorithm is O(n2). 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.
Answered By - rgettman
Answer Checked By - Mildred Charles (JavaFixing Admin)