Finding triplets in an array with a specific sum constraint is a classic algorithmic problem often asked in technical interviews by top companies like Microsoft. In this article, we will break down how to solve the Triplets with Sum in Range problem efficiently using Java, moving from a conceptual understanding to an optimal $O(n^2)$ solution.

1. Problem Understanding

Given an array of integers arr[] and a range defined by two values, l and r, our goal is to count the total number of unique triplets (arr[i], arr[j], arr[k]) such that their combined sum falls inclusively within the range $[l, r]$.

Mathematically, we are looking for triplets where:

$$l \le arr[i] + arr[j] + arr[k] \le r \quad \text{where } 0 \le i < j < k < n$$

Why a Naive Approach Fails

A brute-force approach would use three nested loops to check every possible combination of triplets. This takes $O(n^3)$ time. Given constraints where the array size $n$ can be up to $1000$, $O(n^3)$ operations will result in roughly $10^9$ operations, leading to a Time Limit Exceeded (TLE) error. We need something faster.

2. The Optimal Approach: Sorting & Two Pointers

To optimize the solution to $O(n^2)$ time complexity and $O(1)$ auxiliary space, we can leverage two powerful algorithmic concepts:

  1. Sorting: Bringing order to the array allows us to use pointer-based navigation.

  2. Range Query Transformation: Instead of trying to count sums directly between $l$ and $r$ in one complex step, we can break it down using a prefix-like property:

$$\text{Count}(l, r) = \text{Count}(\text{sum} \le r) - \text{Count}(\text{sum} \le l - 1)$$

How the Two-Pointer Technique Works for Sum $\le \text{val}$

For a fixed element at index i, we set two pointers:

As arr is sorted:

3. Java Implementation

Here is the clean, complete Java solution implementing this logic:

import java.util.Arrays;

class Solution {
    public int countTriplets(int[] arr, int l, int r) {
        // Step 1: Sort the array to enable the two-pointer technique
        Arrays.sort(arr);
        
        // Step 2: Use the property Count(r) - Count(l - 1)
        return countTripletsLessThan(arr, r) - countTripletsLessThan(arr, l - 1);
    }
    
    // Helper function to count how many triplets have a sum <= val
    private int countTripletsLessThan(int[] arr, int val) {
        int n = arr.length;
        int ans = 0;
        
        for (int i = 0; i < n - 2; i++) {
            int j = i + 1;
            int k = n - 1;
            
            while (j < k) {
                int sum = arr[i] + arr[j] + arr[k];
                if (sum > val) {
                    k--; // Sum is too large, move the right pointer down
                } else {
                    // All elements from j+1 to k form valid pairs with arr[i] and arr[j]
                    ans += (k - j);
                    j++; // Move the left pointer up to check next combinations
                }
            }
        }
        return ans;
    }
}

4. Code Breakdown

5. Complexity Analysis