I guess using O(mn) extra space and O(mn log (mn)) sorting time complexity is remotely the optimal solution.