Count Index Triplets Whose Max Minus Min Is at Most d

You are given an integer array arr and a non-negative integer d. A triplet is a choice of three distinct positions i < j < k of arr. Its spread is the largest of arr[i], arr[j] and arr[k] minus the smallest of them. A triplet is valid when its spread is at most d.

Return the number of valid triplets.

Function Signature

def count_triplets(arr: list[int], d: int) -> int:

Rules

• Triplets are identified by their positions, not their values. Two triplets are different when their sets of positions differ, even if they hold the same values, and each set of three positions is counted once.
• The values in a triplet may be equal. Three equal values have spread 0.
• The bound is inclusive: a triplet whose spread equals d is valid.
• If arr has fewer than three elements, return 0.

Constraints

• 0 <= len(arr) <= 100000
• 0 <= arr[i] <= 10^9
• 0 <= d <= 10^9
• The answer can be as large as C(100000, 3) = 166,661,666,700,000, which exceeds 2^31 - 1. Use a 64-bit integer; the answer stays below 2^53.

Examples

Example 1

Input:  arr = [1, 2, 3, 4, 5], d = 2
Output: 3

The valid triplets hold the values {1, 2, 3}, {2, 3, 4} and {3, 4, 5}. Every other triplet has a spread of at least 3.

Example 2

Input:  arr = [4, 1, 1, 3, 2], d = 1
Output: 1

Only positions 1, 2 and 4, holding 1, 1 and 2, give a spread of at most 1.

Example 3

Input:  arr = [7, 7, 7, 7], d = 0
Output: 4

All four ways to choose three of the four positions are valid, because every triplet has spread 0.

Count Position Triplets With Spread at Most d

Hints

1. Validity depends only on the smallest and largest of the three values; the middle value just has to lie between them.
2. Triplets are counted by positions, so equal values at different positions form different triplets and must not be collapsed.
3. With up to 100,000 elements, checking every triple directly is far too slow, and the count can exceed 2^31 - 1, so keep the total in a 64-bit integer.

Approach

Sort a copy of arr. Reordering does not change the answer: a set of three positions corresponds one-to-one with a set of three indices of the sorted copy that hold the same three values, and validity depends only on those values. In the sorted copy a, an index triple p < q < r is valid exactly when a[r] - a[p] <= d, because a[p] is the smallest and a[r] the largest of the three. Count each valid triple once, at its largest index r. For a fixed r, the admissible smallest indices form a contiguous range [left, r - 1], where left is the smallest index with a[r] - a[left] <= d (a is non-decreasing). Any two indices chosen from those m = r - left indices complete a valid triple with r, so r contributes C(m, 2) = m * (m - 1) / 2. As r grows a[r] never decreases, so left never moves backwards and one two-pointer sweep finds every left in linear time after sorting. Invariant: after the inner loop, left is the first index whose value is within d of a[r]; it never passes r because a[r] - a[r] = 0 <= d. Edge cases: fewer than three elements return 0; d = 0 counts only triplets of equal values; equal values at different positions occupy different sorted indices, so duplicates are counted by position, not collapsed. The total can reach C(100000, 3) = 166,661,666,700,000, so it is accumulated in a 64-bit integer (long in Java, long long in C++), and differences are taken in 64-bit arithmetic.

• Time complexity: O(n log n)
• Space complexity: O(n)