Finding the minimum distance in a table

Question

I have a table of dimension m * n as given below

2    6    9    13
1    4    12   21
10   14   16   -1

Few constraints about this table:

1. Elements in each row is sorted in increasing order (natural ordering).
2. A -1 means the cell is of no significance for the purpose of calculatio, i.e. no element exists there.
3. No element can appear in a row after a -1.
4. All the cells can have either a positive number between 0 and N or a -1.
5. No two cells have the same positive numbe, i.e. a -1 can appear multiple times but no other number can.

Question: I would like to find a set S of n numbers from the table where the set must contain only one number from each row and the max(S) - min(S) is as small as possible.

For e.g. the above table gives me S = 12,13,14.

I would really appreciate if this can be solved. My solution is complicated and it takes O(m^n) and this is too much. I want an optimal solution.

Answer 1

Here is a brute force O((m*n)^2 * nlog(m)) algorithm that I can prove works:

min <- INFINITY
For each 2 numbers in different rows, let them be a,b
   for each other row: 
        check if there is a number between a and b
    if there is a matching number in every other row:
        min <- min{min,|a-b|}

Explanation:
Checking if there is a number between a and b can be done using binary search, and is O(logm)
There are O((n*m)^2) different possibilities for a,b.

The idea is to exhaustively check the pair which creates the maximal difference, and check if it gives a "feasible" solution(all other elements in this solution are in range [a,b]), and get the pair that minimizes the difference between all "feasible" solutions .

---

EDIT: removed the 2nd solution I proposed, which was greedy and wrong.