Best Meeting Point


  • 0

    Click here to see the full article post


  • 0
    Z

    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.


  • 0

    Yup, you can use the famous selection algorithm to optimize Solution #3 to O(mn), but you don't have to. I mentioned that briefly in Solution #4.


  • 0
    J

    For #3, why we do not need to sort rows?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.