Coding Daily

Problem Description

Given a sorted array of integers and a target value, count the number of triplets (i, j, k) such that arr[i] + arr[j] + arr[k] = target and i < j < k.

Example:

Input: arr[] = [-3, -1, -1, 0, 1, 2], target = -2
Output: 4
Explanation: The valid triplets are:
- (-3) + 0 + 1 = -2
- (-3) + (-1) + 2 = -2
- (-3) + (-1) + 2 = -2
- (-1) + (-1) + 0 = -2

Solution Code

import java.util.Arrays;

class Solution {
    public int countTriplets(int[] arr, int target) {
        Arrays.sort(arr); // Ensure the array is sorted
        int n = arr.length;
        int count = 0; // To store the count of valid triplets

        for (int i = 0; i < n - 2; i++) {
            int left = i + 1; // Pointer to the element next to arr[i]
            int right = n - 1; // Pointer to the last element

            while (left < right) {
                int sum = arr[i] + arr[left] + arr[right]; // Calculate the current sum

                if (sum == target) {
                    // If the sum equals the target, count all valid triplets
                    if (arr[left] == arr[right]) {
                        // If all elements between left and right are the same, calculate the number of triplets
                        int m = right - left + 1;
                        count += m * (m - 1) / 2; // Combination formula for mC2
                        break;
                    } else {
                        // Count all triplets with the same values as arr[left] and arr[right]
                        int leftVal = arr[left];
                        int rightVal = arr[right];
                        int leftCount = 0, rightCount = 0;

                        while (left < n && arr[left] == leftVal) {
                            left++;
                            leftCount++;
                        }

                        while (right >= 0 && arr[right] == rightVal) {
                            right--;
                            rightCount++;
                        }

                        count += leftCount * rightCount;
                    }
                } else if (sum < target) {
                    left++; // Move left pointer to increase the sum
                } else {
                    right--; // Move right pointer to decrease the sum
                }
            }
        }

        return count;
    }
}

Hint

Sort the array and use a nested loop with two pointers to efficiently count the number of triplets whose sum equals the target.

Approach Name

Two-Pointer Technique with Sorting

Intuition

By sorting the array, we can fix one element and use two pointers to find the other two elements that sum up to the target. This reduces the problem to a two-sum problem for each fixed element.

Algorithm

Sort the array in ascending order.
Iterate through the array, fixing the first element of the triplet.
Use two pointers, left and right, to find the other two elements such that the sum of the three elements equals the target.
If the sum equals the target, count all valid triplets and handle duplicates.
If the sum is less than the target, move the left pointer to the right.
If the sum is greater than the target, move the right pointer to the left.
Return the total count of valid triplets.

Test Input

-3 -1 -1 0 1 2, -2

Complexity Analysis

Time Complexity: O(n²), where n is the number of elements in the array. Sorting takes O(n log n), and the nested loop with two pointers takes O(n²).
Space Complexity: O(1), as we are using a constant amount of extra space.

This solution efficiently counts the number of triplets whose sum equals the target using sorting and a two-pointer approach, ensuring optimal performance for the given constraints.

Count all triplets with given sum in sorted array