Count Triplets With Sum Smaller Than X — Problem & Solution
Count Triplets With Sum Smaller Than X solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Triplets With Sum Smaller Than X is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Adobe and Samsung interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Two Pointers
- Asked at: Amazon, Adobe, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array arr and an integer target, count the triples of indices (i, j, k) with i < j < k whose values sum to strictly less than target.
Example 1
Input: arr = [-2,0,1,3], target = 2
Output: 2
Explanation: (-2,0,1) sums to -1 and (-2,0,3) sums to 1. Both are below 2.
Example 2
Input: arr = [5,1,3,4,7], target = 12
Output: 4
Explanation: (1,3,4), (1,3,5), (1,3,7) and (1,4,5).
Example 3
Input: arr = [1,2,3], target = 5
Output: 0
Constraints
3 <= arr.length <= 200-1000 <= arr[i] <= 1000-3000 <= target <= 3000
Hints for Count Triplets With Sum Smaller Than X
Hint 1
Sorting does not change which triples exist — only how easily you can count them.
Hint 2
Fix the smallest element, then two-pointer over the rest.
Hint 3
When
s[i] + s[lo] + s[hi] < target, every index betweenloandhialso works withs[lo]— that ishi - lotriples at once.
How to solve Count Triplets With Sum Smaller Than X
Sort, fix the first element, and two-pointer the remaining suffix. The key counting trick is that a single successful comparison settles a whole block of triples at once.
Approach
- Sort
arrascending. - For each
i, setlo = i + 1andhi = n - 1. - If
s[i] + s[lo] + s[hi] < target, then pairings[lo]with any ofs[lo+1] … s[hi]also stays under the target — addhi - loand advancelo. - Otherwise the sum is too big, so decrement
hi.
Why it works
The array is sorted, so s[lo] + s[m] <= s[lo] + s[hi] for every m between lo and hi. One passing comparison therefore certifies all hi - lo of those triples, and each pointer moves at most n times, keeping the inner loop linear.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Adding
1instead ofhi - loturns the counting into an O(n³) enumeration in disguise — and undercounts. - Strictly less than, not less than or equal — a triple that hits
targetexactly does not count.
Reference solution
Python
from typing import List
def countTriplets(arr: List[int], target: int) -> int:
s = sorted(arr)
total = 0
for i in range(len(s) - 2):
lo, hi = i + 1, len(s) - 1
while lo < hi:
if s[i] + s[lo] + s[hi] < target:
total += hi - lo
lo += 1
else:
hi -= 1
return totalJava
public static int countTriplets(int[] arr, int target) {
int[] s = arr.clone();
Arrays.sort(s);
int total = 0;
for (int i = 0; i < s.length - 2; i++) {
int lo = i + 1, hi = s.length - 1;
while (lo < hi) {
if (s[i] + s[lo] + s[hi] < target) { total += hi - lo; lo++; }
else hi--;
}
}
return total;
}C++
int countTriplets(vector<int>& arr, int target) {
vector<int> s = arr;
sort(s.begin(), s.end());
int total = 0;
for (int i = 0; i + 2 < (int) s.size(); i++) {
int lo = i + 1, hi = (int) s.size() - 1;
while (lo < hi) {
if (s[i] + s[lo] + s[hi] < target) { total += hi - lo; lo++; }
else hi--;
}
}
return total;
}JavaScript
var countTriplets = function(arr, target) {
var s = arr.slice().sort(function(a, b) { return a - b; });
var total = 0;
for (var i = 0; i < s.length - 2; i++) {
var lo = i + 1, hi = s.length - 1;
while (lo < hi) {
if (s[i] + s[lo] + s[hi] < target) { total += hi - lo; lo++; }
else hi--;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms