Count all triplets with given sum in sorted array

JavaView on GFG

Time: O(n^2)

Space: O(1)

Intuition

Sort array. For each element, use two pointers on the rest. Count pairs summing to target-arr[i].

Algorithm

1For each i: lo=i+1, hi=n-1.
2If arr[lo]+arr[hi] < target-arr[i]: lo++. If > target: hi--. If ==: count pairs (handle duplicates).

Common Pitfalls

•When sum matches, count all valid (lo,hi) pairs with those values (use while loops to count duplicates).

Count all triplets with given sum in sorted array.java

Java

// Approach: For each element as the first, use two pointers on the remaining sorted array.
// Time: O(n^2) Space: O(1)
class Solution {
    public int countTriplets(int[] arr, int target) {
        int count = 0;
        for (int i = 0; i < arr.length - 2; i++) {
            int j = i + 1, k = arr.length - 1;
            while (j < k) {
                int s = arr[i] + arr[j] + arr[k];
                if (s == target) {
                    if (arr[j] == arr[k]) {
                        count += (k - j + 1) * (k - j) / 2;
                        break;
                    }
                    int left = 1, right = 1;
                    while (j + 1 < k && arr[j] == arr[j + 1]) {
                        j++;
                        left++;
                    }
                    while (k - 1 > j && arr[k] == arr[k - 1]) {
                        k--;
                        right++;
                    }
                    count += left * right;
                    j++;
                    k--;
                } else if (s < target)
                    j++;
                else
                    k--;
            }
        }
        return count;
    }
}

Was this solution helpful?