Math Bazooka | 1 liner | Earthmover Distance Solution
Today we will be nuking mosquitos by using the Earthmover distance. \n\nExcluding an import, this yields a 1-liner.\n\nIs that overkill? Yes, absolutely.\n\n\nf
Today we will be nuking mosquitos by using the [Earthmover distance](https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.wasserstein_distance.html). \n\nExcluding an import, this yields a 1-liner.\n\nIs that overkill? Yes, absolutely.\n\n```\nfrom scipy.stats import wasserstein_distance as EMD\nclass Solution:\n    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n        return round( len(seats)*EMD(seats, students) )\n```\n\n# Intuition\n\n**TLDR:** The Earthmover distance (EMD) is a measure of statistical distance coming from the theory of optimal transport which basically tells you the minimal effort it would take to reshape one probability distribution into another. Reframing our inputs as probability distributions, we can compute their EMD and rescale to get the answer in 1-line. You can learn more about the specific implementation the code used from the [documentation](https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.wasserstein_distance.html).\n\n**Q:** But where are the probability distributions?\n**A:** To turn our `seats` position data into a probability distribution, we can just imagine we pick seats at random. So each seat has a uniform $$1/n$$ chance of being selected. That\'s it, that\'s the distribution. It\'s called the *empirical distribution*. We can do the same thing for `students`. \n\nIn our case, the EMD of two 1D empirical distributions with equal number of points will tell us on ***average*** how much each point will need to move in the optimal transport plan. The scipy implemention with defaults assumes this, so that means `EMD(seats,students)` equals `answer/n`. So if we just multiply by the number of points (i.e. array length) then we should have the answer. However, because of the limited precision of floats, we\'ll need to actually round after that multiplication. \n\n# Complexity\n![image.png](https://assets.leetcode.com/users/images/d8d236fc-0e16-4251-a922-a5723a49327e_1680342490.2423034.png)\nDidn\'t vet the implementation so dunno. The differences of sorted values solution is surely much faster though since it avoids floats and requires no import. It would be interesting to see how that solution fares against the EMD approach if the seat/student positions were allowed to be floats.\n\n**Bonus Background:** Among many reasons the EMD is nice is because it is well-defined for higher dimensions (possibly infinite), curved geometry (spheres), and wacky distributions (you can compare discrete and continuous distributions and mixes of the two). It has lots of applications ranging from statistics, physics, biology, and machine learning as well (see Wasserstein GANs).\n\n**Minor technical notes:** I\'ve been saying probability distribution but I really mean probability measure to be precise. \n\n
['Math', 'Probability and Statistics', 'Python3']