In an $n \times n$ matrix $A$, a saddlepoint is defined as an entry that is the maximum in its row and the minimum in its column. A strict saddlepoint is one where no other entry in its row or column shares the same value. Finding a non-strict saddlepoint can require $\Theta(n^2)$ matrix queries in the worst case, while a strict saddlepoint can be found using only $O(n)$ queries.
In 1991, Bienstock, Chung, Fredman, Schäffer, Shor, and Suri, along with Byrne and Vaserstein independently, showed that a strict saddlepoint can be found (or certified as non-existent) in $O(n \log n)$ time with $O(n)$ matrix queries. In 2024, Dallant, Haagensen, Jacob, Kozma, and Wild introduced an $O(n \log^* n)$-time algorithm, followed by an optimal randomized algorithm that runs in $O(n)$ time with high probability. However, the question of whether a deterministic $O(n)$ time solution was possible remained open.
Here, we resolve this question by presenting a simple deterministic algorithm that finds a strict saddlepoint or reports its absence in optimal $O(n)$ time. Our algorithm combines elementary components from prior approaches with linear-time selection from a collection of sorted lists.