Count Index Triplets Whose Max Minus Min Is at Most d
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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`.
Overview: A counting problem that asks how many triplets of positions in an integer array have a spread, the largest value minus the smallest, of at most d. It tests handling duplicates and inclusive bounds, producing a count that can exceed 32 bits, and meeting time limits for arrays of up to 100,000 elements.
Read the full IBM Software Engineer interview experience this question came from
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.
### 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`. Return it as a 64-bit integer (`long` in Java, `long long` in C++); the answer always stays below `2^53`.
### Examples
**Example 1**
```text
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**
```text
Input: arr = [4, 1, 1, 3, 2], d = 1
Output: 1
```
Only the 0-indexed positions `1`, `2` and `4`, holding `1`, `1` and `2`, give a spread of at most `1`.
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 (long in Java, long long in C++). The answer stays below 2^53.
- Triplets are counted by positions i < j < k; the spread bound is inclusive; return 0 when arr has fewer than three elements.
Examples
Input: ([1, 2, 3, 4, 5], 2)
Expected Output: 3
Explanation: Source Example 1: only the value runs {1, 2, 3}, {2, 3, 4} and {3, 4, 5} have spread at most 2.
Input: ([4, 1, 1, 3, 2], 1)
Expected Output: 1
Explanation: Source Example 2: unsorted input; only positions 1, 2, 4 (values 1, 1, 2) qualify, while no three adjacent positions do.
Hints
- Validity depends only on the smallest and largest of the three values; the middle value just has to lie between them.
- Triplets are counted by positions, so equal values at different positions form different triplets and must not be collapsed.
- 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.