Lexicographically smallest down-right path in matrix

Question

Here is the problem which I thought was simple dynamic programming, which is however not the case.

Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path from top left to right bottom while moving right or down only. If we sort all values visited in this path it should be lexicographically smallest.

I thought smallest sum path will be the answer, but it need not be true.

Answer 1

Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ matrix. (This requires a proof, but intuitively seems correct.)

To implement this algorithm efficiently, we need an efficient data structure for the two-dimensional range minimum query problem. Brodal, Davoodi and Rao give, in their paper On Space Efficient Two Dimensional Range Minimum Data Structures, a data structure that answers queries in $O(1)$ time, after $O(NM)$ preprocessing.

Actually, we need to find the minimum of a rectangle without two of its corners, but this domain can be written as the union of three rectangles, so such a query can also be answered in constant time.

Using such a data structure, we obtain an algorithm running in linear time $O(NM)$.

In fact, it suffices to use a much simpler data structure supporting one-dimensional range minimum queries; see Fischer, Optimal Succinctness for Range Minimum Queries for appropriate references. Suppose that $N \leq M$. Using a range minimum query data structure on each row, we can answer a two-dimensional range minimum query in time $O(N)$. Since the algorithm above makes only $O(N+M) = O(M)$ such queries, the overall complexity is still $O(NM)$.