After reading, I have two questions pending on this approach:
a. I could understand that for 1-d scenario, it is optimal to find "median". However, this approach applies this theory to 2-d senario: "Then we calculate the total distance as the sum of two independent 1D problems."
How to prove 1-d scenario correctness to a 2-d scenario? Or more generally, may I apply 1-d scenario correctness to an n-d scenario?
b. Honestly, the solution specifically said that "in the code above we do not need to sort rows". Could anyone give me some clue on why we ignore this soring on rows?
Thanks a lot !!