Problem related to maximum Manhattan Distance

help
,
1

Given N points which are d-dimensional, return the maximum Manhattan distance between 2 points.
I have written a code which runs in O(d*N^2) and gets a TLE.
Can anyone suggest me a faster solution?
Problem link: SPOJ.com - Problem DISTANCE

Thanks in advance :slight_smile:

2

I haven’t tried this yet, but here’s a question that I think will be helpful:

Take any integer coordinate, C. What do the set of coordinates whose Manhattan Distance from C is precisely 5 look like? Precisely 6? 7? What’s the pattern, and is there a way of using this pattern to determine (perhaps with a little pre-processing of the coordinates) the coordinate in our list that is furthest from C in less than O(N)?

Edit:

Lol - just noticed that that this is not necessarily two-dimensional - ignore the above - ouch!