Search code examples
algorithmminimum

Finding the minimum distance in a table

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.

Solution
    1. Put positions of all first elements of each row into priority queue (min-heap).
    2. Remove smallest element from the queue and replace it with the next element from the same row.
    3. Repeat step 2 until no more elements different from "-1" are left in some row. Calculate max(S) - min(S) for each iteration and if it is smaller than any previous value, update the best-so-far set S.

    Time complexity is O(m*n*log(m)).