LC: 296. Best Meeting Point - spiralgo/algorithms GitHub Wiki
The Essence: As Manhattan Distance has two components (rows distance, columns distance), we can reduce the question from 2D to 1D array problem. We can first solve 1D problem for rows and then the other 1D problem for columns independantly.
Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
We will use the median, instead of the mean of an array to find the minimum distance between the two points. You can find the detailed explanation below.
Details:
Why do we use the median instead of the mean of an array?
As quoted from Wikipedia:
The median can be used as a measure of location when one attaches reduced importance to extreme values, typically because a distribution is skewed, extreme values are not known, or outliers are untrustworthy, i.e., may be measurement/transcription errors.
Imagine a factory has developed some robots and wants to know about the general efficiency of the robots.
Few of the robots have been produced with defuncts, their total performance looks like this:
[2, 144, 126, 108, 117]
To use the mean to calculate the general performance would yield: (2+144+126+108+117)/5 = 99.4
97.6 is not a good representation for the general performance of the machines. The single one with the defunct has too much weight in the calculation, where all the other robots have a performance higher than this, skewing the results.
Then they try median instead. Median is the number in the middle of an array when the numbers are sorted in ascending order.
2, 108, 117, 126, 144
In this case, 117 can represent the robots better than the general mean distribution.
Here, you can find the detailed explanation of implementations: https://github.com/spiralgo/algorithms/pull/364