Total Distances Along a Route

Medium

Bus stops stand along a straight road; their coordinates are given in stops, sorted in non-decreasing order (several stops may coincide). For every stop i, find the sum of distances from it to all the other stops, that is, the sum of |stops[i] - stops[j]| over all j ≠ i. Return these sums as an array in the same order.

Example 1

stops=[1, 3, 8] → [9, 7, 12]

From stop 1: 2 + 7 = 9. From 3: 2 + 5 = 7. From 8: 7 + 5 = 12.

Example 2

stops=[4, 4, 6, 10] → [8, 8, 8, 16]

From either 4: 0 + 2 + 6 = 8. From 6: 2 + 2 + 4 = 8. From 10: 6 + 6 + 4 = 16.

Constraints

2 ≤ len(stops) ≤ 10⁵
1 ≤ stops[i] ≤ 10⁴
stops[i] ≤ stops[i + 1]

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Prefix Sum

Similar problems

A Stretch Divisible by k Medium The Growing Grab Limit Medium Stretches With k Odd Numbers Medium Split Into Equal-XOR Halves Medium Segments With an Odd Sum Medium

Input

stops=[1, 3, 8]

Expected

[9, 7, 12]

Run checks the first 3 tests in your browser. Submit checks all 65 tests on the server, hidden ones included.