Count Triplets With Sum Smaller Than X — Medium Problem & Solution

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

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

1. Sort arr ascending.
2. For each i, set lo = i + 1 and hi = n - 1.
3. If s[i] + s[lo] + s[hi] < target, then pairing s[lo] with any of s[lo+1] … s[hi] also stays under the target — add hi - lo and advance lo.
4. 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 1 instead of hi - lo turns the counting into an O(n³) enumeration in disguise — and undercounts.
• Strictly less than, not less than or equal — a triple that hits target exactly 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium