CODEWITHSUNDEEP
algorithmminimum
dharam
dharam

Reputation: 8106

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.

Upvotes: 5

Views: 352

Answers (2)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

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

Upvotes: 2

amit
amit

Reputation: 178521

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.

Upvotes: 3

Related Questions