# Lexicographically smallest down-right path in matrix

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.

• "If we sort all values visited in this path it should be lexicographically smallest". Can you give a non-trivial example? I guess 2 by 2 is enough. Feb 12 '19 at 4:38

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)$$.

• I got the solution, but I did not understand how can we find the minimum of a matrix in O(1) time. Feb 12 '19 at 7:41
• It’s explained in the paper I link to. Feb 12 '19 at 9:27
• I haven’t read it, so you’re better placed to answer this question... but you can also use one-dimensional data structures, which are quite simple, and still get an $O(NM)$ complexity, since you can afford to spend $O(\min(N,M))$ time at every step. Feb 12 '19 at 10:45
• I think the overall average time complexity would be 2*n^2. Am I correct? if we take a square matrix. Feb 12 '19 at 11:26
• It should be $O(n^2)$. Feb 12 '19 at 11:38