Count Index Triplets Whose Max Minus Min Is at Most d

Quick 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.

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.

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 Index Triplets Whose Max Minus Min Is at Most d

Quick Overview