Funcia
Lv.1mathprefix-sumsorting

Total Pairwise Distance

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

houses gives the positions of n houses on a straight road (unsorted, possibly repeated). Return the sum of |houses[i] - houses[j]| over all pairs i < j.

Examples

housesresult
[1, 3, 6]10
[5, 5, 5]0
[8, 0, 2, 2]24

Example 1 — 2 + 5 + 3 = 10.

Efficiency

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

Function signature

solution(houses: int[]) → long

Constraints

  • 2≤2 \le houses.length ≤200,000\le 200{,}000
  • 0≤0 \le houses[i] ≤108\le 10^8
  • The answer may not fit in 32 bits; use a 64-bit integer (long).

Expected complexity

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

Examples

housesExpected
[1,3,6]10
[5,5,5]0
[8,0,2,2]24

Hint

Hint

Sort the positions first. In sorted order, house j contributes j⋅xj−(x0+⋯+xj−1)j \cdot x_j - (x_0 + \dots + x_{j-1}) against all earlier houses; keep a running prefix sum and use 64-bit integers. Adding every pair's distance 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 251186 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

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

No result yet. Run or submit your code.