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.