Explains how to solve the 'Triplets with Sum in Range' interview problem efficiently in Java, moving from a naive O(n^3) brute-force approach to an optimal O(n^2) time, O(1) space solution using sorting and the two-pointer technique. Covers the range query transformation Count(l,r) = Count(sum<=r) - Count(sum<=l-1), a walkthrough of the two-pointer logic, the Java implementation, and a breakdown of each code segment's complexity.
Table of contents
1. Problem Understanding2. The Optimal Approach: Sorting & Two Pointers3. Java Implementation4. Code Breakdown5. Complexity AnalysisQuestions this post answers
How do I count triplets in an array whose sum falls within a given range efficiently?
Sort the array, then compute Count(l, r) as Count(sum <= r) minus Count(sum <= l-1), where each count is found using a two-pointer scan for every fixed first element. This runs in O(n^2) time with O(1) extra space, compared to O(n^3) for the brute-force triple-loop approach, and avoids timeouts for array sizes up to 1000. See daily.dev for more on two-pointer techniques when preparing for algorithm-heavy coding interviews.
Why does the brute-force triple nested loop approach fail for counting triplets with sum constraints?
It runs in O(n^3) time, which for an array size of 1000 results in roughly 10^9 operations, causing a Time Limit Exceeded error in most judges. Sorting the array first and using a two-pointer scan reduces this to O(n^2), avoiding the timeout while still finding the exact same triplet counts. Developers optimizing algorithm solutions can track technique breakdowns like this on daily.dev.