Best Meeting Point


One potential optimization for Solution #3: since we only care about the median value, we could use "find kth smallest element" to find the median of column in O(N).
C++ STL has nth_element which rearranges the elements in the range in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. So the time complexity of Solution #3 would be O(mn) I think.
AC C++ code in the pic attached.

@jonsnow1984 Because when you append elements in
rows
, it is already sorted. In other words, you are inserting the row index of every element. For example, you always insert 0's, then insert 1's inrows
.