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?


  • 0
    D

    @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 in rows.


Log in to reply
 

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