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.

  • $\begingroup$ "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. $\endgroup$
    – John L.
    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)$.

  • $\begingroup$ I got the solution, but I did not understand how can we find the minimum of a matrix in O(1) time. $\endgroup$ Feb 12 '19 at 7:41
  • $\begingroup$ It’s explained in the paper I link to. $\endgroup$ Feb 12 '19 at 9:27
  • $\begingroup$ 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. $\endgroup$ Feb 12 '19 at 10:45
  • $\begingroup$ I think the overall average time complexity would be 2*n^2. Am I correct? if we take a square matrix. $\endgroup$ Feb 12 '19 at 11:26
  • 1
    $\begingroup$ It should be $O(n^2)$. $\endgroup$ Feb 12 '19 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.