2
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2019 at 4:38

1 Answer 1

3
$\begingroup$

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

$\endgroup$
5
  • $\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, 2019 at 7:41
  • $\begingroup$ It’s explained in the paper I link to. $\endgroup$ Feb 12, 2019 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, 2019 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, 2019 at 11:26
  • 1
    $\begingroup$ It should be $O(n^2)$. $\endgroup$ Feb 12, 2019 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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