Kth Smallest Order Pair Spread

In statistical arbitrage and spread trading at Jane Street and Jump Trading, quantitative researchers analyze the distribution of pairwise price spreads across recorded transactions.

Given an integer array of recorded execution prices prices of size $N$, and an integer $k$, the pairwise spread between any two distinct executions $i$ and $j$ ($0 \le i < j < N$) is $|prices[i] - prices[j]|$.

There are $\frac{N(N - 1)}{2}$ total pairs.

Your Task

Implement smallest_distance_pair(prices: list[int], k: int) -> int that determines the $k$-th smallest pairwise spread in $\mathcal{O}(N \log N + N \log(\max(prices) - \min(prices)))$ time.

Constraints

• $2 \le N \le 10^5$
• $0 \le prices[i] \le 10^6$
• $1 \le k \le \frac{N(N - 1)}{2}$

Examples

prices = [1, 3, 1]
k = 1
# Pairs: (1, 3) diff 2; (1, 1) diff 0; (3, 1) diff 2.
# Sorted spreads: [0, 2, 2]. 1st smallest is 0.
# Output: 0

prices = [1, 6, 1]
k = 3
# Spreads: [0, 5, 5]. 3rd smallest is 5.
# Output: 5