problem statement : https://practice.geeksforgeeks.org/problems/count-the-triplets4615/1#
Given an array of distinct integers. The task is to count all the triplets such that the sum of two elements equals the third element.
Example 1:
Input:
N = 4
arr[] = {1, 5, 3, 2}
Output: 2
Explanation: There are 2 triplets:
1 + 2 = 3 and 3 +2 = 5
Example 2:
Input:
N = 3
arr[] = {2, 3, 4}
Output: 0
Explanation: No such triplet exits
Your Task:
You don't need to read input or print anything. Your task is to complete the function countTriplet() which takes the array arr[] and N as inputs and returns the triplet count
Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 103
1 ≤ arr[i] ≤ 105
Solution Contains :
- Solution using HashMap [space complexity O(n)]
- Solution using 2 pointers [space complexity O(1)]
Solution using HashMap
This solution is in java
import java.util.*;
class Solution {
int countTriplet(int a[], int n) {
// code here
int cnt = 0;
HashMap<Integer, Integer> map = new HashMap<>();
// value -> index
for(int i = 0; i < n; i++) {
// since it is distinct so no need to worry about duplicate values
map.put(a[i], i);
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
Integer found = map.get(a[i] + a[j]);
if(found != null && found != i && found != j)
cnt ++;
}
}
return cnt;
}
}
Solution using two pointers
import java.util.*;
/**
* We will check for each number and say wether it could be decomposed into 2
* such that those 2 numbers after addition ends up being the source number.
*/
// complexity :
// time : O(n^2)
// space : O(1)
public class TwoPointerSolution {
int countTriplet(int a[], int n) {
// code here
int cnt = 0;
Arrays.sort(a);
for(int i = 0; i < n; i++) {
cnt += decompose(a, a[i], 0, i-1);
}
return cnt;
}
int decompose(int[] a, int source, int from, int to) {
if(to >= a.length || from < 0 || from >= to) return 0;
int cnt = 0;
while(from < to) {
int testSum = a[from] + a[to];
if(testSum > source) {
to--;
} else if(testSum < source) {
from++;
} else {
cnt++; // inc. count
to--; // shrink window
from++; // as every elemet is distinct.
}
}
return cnt;
}
}
Top comments (0)