Count triplets with sum less than given value

Given an array with distinct elements, count triplets whose sum is less than a given value.

Example

Input: arr[] = {3, 5, 7, 9}
Sum = 6
Output: 1
Explanation: Below is the triplet with a sum less than 6 (3, 5, 7)

Example

Input: arr[] = {-1, 2, 4, 6, 8}
Sum = 10
Output: 5
Explanation: Below are triplets with a sum less than 10 (-1, 2, 4), (-1, 2, 6), (-1, 4, 6), (2, 4, 6), (-1, 2, 8)

Algorithm

1. Sort the array in ascending order.
2. Initialize a variable to keep track of the count of such triplets.
3. Use two nested loops to select two elements from the array.
4. Use a while loop to select the third element from the remaining elements.
5. Check if the sum of the selected triplet is less than the given value. If it is, increment the count by the number of valid third elements.
6. Continue the loops until all possible triplets are considered.
7. Return the count of triplets that satisfy the condition.

Complexity

• Time Complexity: O(N^2), where N is the number of elements in the array.
• Space Complexity: O(1), because the code uses only a constant amount of extra space.

Code

## Java Code

import java.util.Arrays;

public class CountTripletsWithSumSmaller {
    public static int countTripletsWithSumSmaller(int[] nums, int targetSum) {
        Arrays.sort(nums); // Step 1: Sort the array
        int n = nums.length;
        int count = 0;

        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];

                // Step 4: Check if the sum is smaller than the target
                if (currentSum < targetSum) {
                    count += (right - left + 1); // Corrected counting logic
                    left++;
                } else {
                    right--;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {5, 1, 3, 4, 7};
        int targetSum = 12;
        int result = countTripletsWithSumSmaller(nums, targetSum);
        System.out.println("Count of triplets with sum smaller than " + targetSum + " is " + result);
    }
}

Output

Count of triplets with sum smaller than 12 is 4