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:
Sorting: Bringing order to the array allows us to use pointer-based navigation.
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:
If arr[i] + arr[j] + arr[k] > val, the sum is too large. We decrement k to lower the sum.
If arr[i] + arr[j] + arr[k] <= val, it means all elements between j and k will also form valid triplets with arr[i] and arr[j] because the array is sorted. We can add (k - j) directly to our answer, and then increment j to test the next candidate.
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
Arrays.sort(arr);: This takes $O(n \log n)$ time and arranges the array in ascending order, which is crucial for the pointer logic to work.
countTripletsLessThan(arr, r) - countTripletsLessThan(arr, l - 1): This filters out everything strictly smaller than $l$, leaving precisely the count of triplets whose sums lie in the closed range $[l, r]$.
The while (j < k) loop: Inside the helper method, this efficiently evaluates pairs in $O(n)$ time for every fixed element i, turning an $O(n^3)$ search into an $O(n^2)$ scan.
5. Complexity Analysis