Given a sorted array arr[] and a target value, the task is to count triplets (i, j, k) of valid indices, such that arr[i] + arr[j] + arr[k] = target and i < j < k.
Examples:
Input: arr[] = [-3, -1, -1, 0, 1, 2], target = -2
Output: 4
Explanation: Two triplets that add up to -2 are:
arr[0] + arr[3] + arr[4] = (-3) + 0 + (1) = -2
arr[0] + arr[1] + arr[5] = (-3) + (-1) + (2) = -2
arr[0] + arr[2] + arr[5] = (-3) + (-1) + (2) = -2
arr[1] + arr[2] + arr[3] = (-1) + (-1) + (0) = -2
Input: arr[] = [-2, 0, 1, 1, 5], target = 1
Output: 0
Explanation: There is no triplet whose sum is equal to 1.
Constraints:
3 ≤ arr.size() ≤ 104
-105 ≤ arr[i], target ≤ 105
Approach 01:
-
C++
-
Python
#include <vector>
using namespace std;
class Solution {
public:
int countTriplets(vector<int>& arr, int target) {
int n = arr.size();
int tripletCount = 0;
for (int i = 0; i < n - 2; ++i) {
int leftPointer = i + 1, rightPointer = n - 1;
int requiredSum = target - arr[i];
while (leftPointer < rightPointer) {
int currentSum = arr[leftPointer] + arr[rightPointer];
if (currentSum == requiredSum) {
if (arr[leftPointer] == arr[rightPointer]) {
tripletCount += ((rightPointer - leftPointer) * (rightPointer - leftPointer + 1)) / 2;
break;
} else {
int countLeft = 1, countRight = 1;
while (leftPointer < rightPointer && arr[leftPointer] == arr[leftPointer + 1]) {
++countLeft;
++leftPointer;
}
++leftPointer;
while (leftPointer < rightPointer && arr[rightPointer] == arr[rightPointer - 1]) {
++countRight;
--rightPointer;
}
--rightPointer;
tripletCount += countLeft * countRight;
}
} else if (currentSum > requiredSum) {
--rightPointer;
} else {
++leftPointer;
}
}
}
return tripletCount;
}
};
from typing import List
class Solution:
def countTriplets(self, arr, target):
n = len(arr)
tripletCount = 0
for i in range(n - 2):
leftPointer, rightPointer = i + 1, n - 1
requiredSum = target - arr[i]
while leftPointer < rightPointer:
currentSum = arr[leftPointer] + arr[rightPointer]
if currentSum == requiredSum:
if arr[leftPointer] == arr[rightPointer]:
tripletCount += ((rightPointer - leftPointer) * (rightPointer - leftPointer + 1)) // 2
break
else:
countLeft, countRight = 1, 1
while leftPointer < rightPointer and arr[leftPointer] == arr[leftPointer + 1]:
countLeft += 1
leftPointer += 1
leftPointer += 1
while leftPointer < rightPointer and arr[rightPointer] == arr[rightPointer - 1]:
countRight += 1
rightPointer -= 1
rightPointer -= 1
tripletCount += countLeft * countRight
elif currentSum > requiredSum:
rightPointer -= 1
else:
leftPointer += 1
return tripletCount
Time Complexity:
- Outer Loop:
- The outer loop iterates through the array up to \( n – 2 \) times, where \( n \) is the size of the array. This contributes \( O(n) \).
- Two Pointers:
- For each iteration of the outer loop, the two-pointer technique processes the remaining part of the array. In the worst case, it contributes \( O(n) \) for each iteration of the outer loop.
- Overall Time Complexity:
\( O(n^2) \), as the two-pointer process is nested within the outer loop.
Space Complexity:
- Auxiliary Variables:
- The algorithm uses a few auxiliary variables such as leftPointer, rightPointer, requiredSum, currentSum, countLeft, and countRight, all of which require \( O(1) \) space.
- Overall Space Complexity:
\( O(1) \), as no additional data structures are used.