A city has parcel lockers at grid points lockers[i] = [x, y]. Couriers drive only along the
street grid, so the distance between [x1, y1] and [x2, y2] is |x1 - x2| + |y1 - y2|.
Once a week a courier runs between every unordered pair of distinct lockers (each pair
once). Return the total distance of all these runs. Several lockers may share a spot; such a
pair contributes 0. Fewer than two lockers give 0.
Examples
Input: lockers = [[0, 0], [2, 1], [3, 3]]
Output: 12
Explanation: the pairs cost 3, 6 and 3.
Input: lockers = [[1, 1], [1, 1], [4, 1]]
Output: 6
Explanation: 0 + 3 + 3.
Input: lockers = [[5, -2]]
Output: 0
Constraints
0 <= len(lockers) <= 10**5-10**6 <= x, y <= 10**6- Target: O(n log n) time. Looping over all pairs is far too slow for the largest tests.
Goals
- Split a grid distance into independent row and column parts
- Sum absolute differences of all pairs with a running total
- Replace an O(n^2) pair loop by sorting