title: All points with minimum Manhattan distance from all other given points [Optimized]
body: <p>The problem here is to find set of all integer points which gives minimum sum over all Manhattan distances from given set of points!</p>
  
  <p>For example:</p>
  
  <p>lets have a given set of points { P1, P2, P3...Pn }</p>
  
  <p>Basic problem is to find a point say X which would have minimum sum over all distances from points { P1, P2, P3... Pn }.</p>
  
  <p>i.e. |P1-X| + |P2-X| + ....  + |Pn-X| = D, where D will be minimum over all X.</p>
  
  <p>Moving a step further, there can be more than one value of X satisfying above condition. i.e. more than one X can be possible which would give the same value D. So, we need to find all such X.</p>
  
  <p>One basic approach that anyone can think of will be to find the median of inputs and then brute force the co-ordinates which is mentioned in <a href="https://stackoverflow.com/questions/10402087/algorithm-for-minimum-manhattan-distance">this post</a></p>
  
  <p>But the problem with such approach is: if the median gives two values which are very apart, then we end up brute forcing all points which will never run in given time.</p>
  
  <p>So, is there any other approach which would give the result even when the points are very far apart (where median gives a range which is of the order of 10^9).</p>