Count triplet with sum smaller than a given value

Problem Statement

Given an array of distinct integers and a sum value, count all triplets with sum smaller than the given sum value.

Constraints:

• All elements are distinct
• Return the count of triplets, not the triplets themselves

Example:

• Input: arr = [-2, 0, 1, 3], sum = 2
• Output: 2
• Explanation: Triplets are (-2, 0, 1) and (-2, 0, 3) with sums -1 and 1

Example 2:

• Input: arr = [5, 1, 3, 4, 7], sum = 12
• Output: 4
• Explanation: Triplets with sum < 12: (1,3,4), (1,3,5), (1,3,7), (1,4,5)... count = 4

Approach 1: Brute Force (Three Loops)

Intuition

Check all possible triplets and count those with sum less than the given value.

Algorithm

1. Use three nested loops to select three elements
2. If their sum < target, increment count
3. Return total count

public class Solution {
    public int countTriplets(int[] arr, int sum) {
        int n = arr.length;
        int count = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] < sum) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

• Time Complexity: O(n³) - Three nested loops
• Space Complexity: O(1) - No extra space

Approach 2: Sorting + Two Pointers (Optimal)

Intuition

Sort the array. Fix one element and use two pointers for the remaining two. When we find a valid triplet, all elements between left and right also form valid triplets.

Key Insight

If arr[i] + arr[left] + arr[right] < sum, then all elements from left+1 to right-1 when paired with arr[i] and arr[left] will also satisfy the condition. So we can add (right - left) triplets at once.

Algorithm

1. Sort the array
2. For each element arr[i] (fix first element)
3. Use two pointers: left = i+1, right = n-1
4. If arr[i] + arr[left] + arr[right] < sum:
   • Add (right - left) to count
   • Move left pointer right
5. Else move right pointer left

import java.util.Arrays;

public class Solution {
    public int countTriplets(int[] arr, int sum) {
        int n = arr.length;
        
        if (n < 3) return 0;
        
        Arrays.sort(arr);
        
        int count = 0;
        
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                int currentSum = arr[i] + arr[left] + arr[right];
                
                if (currentSum < sum) {
                    // All elements from left+1 to right form valid triplets
                    count += (right - left);
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return count;
    }
}

Dry Run Example

Why This Works

Complexity Analysis

• Time Complexity: O(n²) - Sorting O(n log n) + Two pointer for each element O(n²)
• Space Complexity: O(1) - In-place (or O(n) depending on sort)

Variation: Print All Triplets

Variation: Count Triplets with Sum Greater Than Value

Variation: Count Triplets with Sum in Range [low, high]

Key Takeaways

1. Two Pointer Technique: After sorting, two pointers efficiently find valid pairs
2. Batch Counting: When one triplet is valid, count all valid triplets between pointers
3. Key Insight: If arr[left] + arr[right] < target, all elements between them also work
4. Sorting Requirement: Two-pointer approach only works on sorted arrays
5. Time Trade-off: O(n³) to O(n²) is significant improvement
6. Similar Problems: Count pairs with sum < K, Count quadruplets, etc.