Funcia
Lv.1arraysorting

Closest Pair Gap

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

Given an integer array nums, return the minimum of ∣|nums[i] −- nums[j]∣| over all pairs of different positions. Values range from −109-10^9 to 10910^9, so the difference may exceed the 32-bit range.

Examples

numsresult
[4, 9, 1, 32, 13]3
[10, -5]15
[7, 3, 7]0

Efficiency

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

Function signature

solution(nums: int[]) → long

Constraints

  • 2≤2 \le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

Expected complexity

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

Examples

numsExpected
[4,9,1,32,13]3
[10,-5]15
[7,3,7]0

Hint

Hint

After sorting, the closest pair is always adjacent (if a < b < c then c - a > b - a), so check neighbouring pairs only: O(Nlog⁡N)O(N \log N). Compute differences in 64 bits; 109−(−109)10^9 - (-10^9) overflows an int. Comparing all pairs is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

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

Test groups

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

No result yet. Run or submit your code.