Median

There are quite a few

How to find median of unsorted array in O(n) time? (i.e. without sorting)

I think we saw it in CS240, through Quickselect, we can do O(n), but worst case is O(n^2)?

Other codeforce problem

If you want to find a point that minimizes the distance to all other points, you can just use the median. Why?

  • Picture that the points are sorted. As you move your point by 1 to the right, there are n-1 distances that are reduced by 1, and 1 that is increased by 1. So always positive. This is no longer true after you get pass the median.

Okay, why is squared distance minimum the mean then?

  • Squared distance “punishes” being far away much more.
  • The point that perfectly balances out all these penalties is exactly the “center of mass” — the mean.
  • If you go to the right of the mean, the sum of squared distances gets bigger, because those far-away points grow quadratically in penalty.

https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/?envType=daily-question&envId=2025-03-26