Count Triplets With Sum Smaller Than X

Medium
620.

Count Triplets With Sum Smaller Than X

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var countTriplets = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Sorting does not change which triples exist — only how easily you can count them.

  2. Hint 2

    Fix the smallest element, then two-pointer over the rest.

  3. Hint 3

    When s[i] + s[lo] + s[hi] < target, every index between lo and hi also works with s[lo] — that is hi - lo triples 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

  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

Java

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