An Optimal Randomized Algorithm for Finding the Saddlepoint

The saddlepoint of a matrix is an entry that is simultaneously the strict minimum in its column and the strict maximum in its row.

In our SOSA 2024 paper, we showed how to find the (strict) saddlepoint in $O(n \log^* n)$ time, just slightly above the $\Omega(n)$ lower bound. In this paper, we close the gap with a randomized linear-time algorithm ($O(n)$ time in expectation and with high probability).