Show problems as
Classic problem #2615MediumArrayHash TablePrefix Sum

Sum of Distances

Real-world version: Spacing Totals Along The Conveyor
Tracked in this browser only
Read Sum of Distances on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A conveyor carries parts in slots numbered 0, 1, 2, and so on. codes[i] is the part code sitting in slot i, and two slots hold the same part exactly when their codes are equal.

For each slot i, its spacing total is the sum of |i - j| over every other slot j that holds the same part code. A slot whose code appears in no other slot has a spacing total of 0.

Return an array holding the spacing total of every slot, in slot order.

Examples

Example 1

Input
codes = [4, 9, 4, 4, 6]
Output
[5, 0, 3, 4, 0]

Part 4 sits in slots 0, 2 and 3. Slot 0 is 2 and 3 away from the other two, giving 5; slot 2 is 2 and 1 away, giving 3; slot 3 is 3 and 1 away, giving 4. Parts 9 and 6 appear once each, so their slots score 0.

Example 2

Input
codes = [3, 3, 3, 3]
Output
[6, 4, 4, 6]

Every slot holds the same part. Slot 0 is 1, 2 and 3 away from the others, giving 6, and slot 1 is 1, 1 and 2 away, giving 4.

Example 3

Input
codes = [7, 1, 4, 2, 9]
Output
[0, 0, 0, 0, 0]

All five codes are different, so no slot has a partner and every spacing total is 0.

Constraints

  • 1 <= codes.length <= 10^5
  • 0 <= codes[i] <= 10^9
  • The largest spacing total these bounds allow is below 5 * 10^9, so a 32-bit integer type is not wide enough to hold one.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def spacing_totals(codes: list[int]) -> list[int]:
Java
public long[] spacingTotals(int[] codes)

More on the same topics