Funcia
Lv.2binary-searchparametric-searchsortingtwo-pointers

K-th Smallest Pair Distance

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

pos[i] is the position of house i on a straight road. Among all N(N−1)/2N(N-1)/2 pairs of distinct houses, the distance of a pair is the absolute difference of their positions. Return the k-th smallest pair distance (pairs with equal distance are counted separately; several houses may share a position).

Examples

poskresult
[1, 3, 1]10
[1, 6, 1]35
[9, 2, 5, 14]47

Example 1 — Distances 2, 0, 2.

Example 2 — Distances 0, 5, 5.

Example 3 — Distances 3, 4, 5, 7, 9, 12.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(pos: int[], k: long) → int

Constraints

  • 2≤N=2 \le N = pos.length ≤50,000\le 50{,}000
  • 0≤0 \le pos[i] ≤106\le 10^6
  • 1≤1 \le k ≤N(N−1)/2\le N(N-1)/2 (may exceed a 32-bit integer)

Expected complexity

Time
O(N log N + N log V)
Space
O(1)

Examples

poskExpected
[1,3,1]10
[1,6,1]35
[9,2,5,14]47

Hint

Hint

Do not enumerate the ~1.2⋅1091.2 \cdot 10^9 pairs. Sort the positions and binary search the answer d: the number of pairs with distance ≤ d is counted in O(N)O(N) with two pointers (for each r, advance l while pos[r] - pos[l] > d, then add r - l). The smallest d whose count is ≥ k is the answer. Total O(Nlog⁡N+Nlog⁡V)O(N \log N + N \log V).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251020 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.