Solution of Exploding Kittens

We first observe that the problem is independent for each dimension.
Therefore we should solve the problem in a 1 dimensional space and the same principle applies to all dimensions.
For the 1D problem, we sort the elements in ascending order of the (only) coordinate and then we can use partial sums to the left and to the right to compute the manhattan distance from one point to all the others in O(M) in total. We just need to take care that we add the manhattan distance to the correct initial point (as the order may differ when sorting on different axis).
Therefore the algorithm is O(N * M * logM) orO(N * M) using the integer property of coordinates and radix / bucket sort.

Questions?

Sponsors Gold