3

I came across a problem but not able to get a better approach than O(m X n)

A 2D array contains column wise sorted array, Is there any way to choose one element from each column and create a row such that the difference of maximum and minimum element in that row should be minimum. for example

A = 1  2  5
    3  4  15
    7 11  17

The answer should be 2 as u can choose 3 from first col, 4 from second and 5 from third making row 3 4 5 making max - min 2.

Is there a way to get this in O(Row * Col)

Ps: Its not from any ongoing competition.

9
  • 3
    You have to inspect every element, so ... Aug 26, 2016 at 11:06
  • You have to inspect every element (Oliver Charlesworth) - well, if there was one column starting with a value that sorts after the last value of all other columns and another with a last value to come before the first values of every other, you would be done with 2(n-1) comparisons. (Not seeing how this might lead to a fast approach. "Someone" should establish/argue a worst case.)
    – greybeard
    Aug 26, 2016 at 12:50
  • Are the values unique in each row/column/in the whole matrix?
    – greybeard
    Aug 26, 2016 at 18:20
  • I have updated the question. Aug 29, 2016 at 5:23
  • I have updated the question sadly, so much that it invalidates previous answers, if not up-votes and favourites. I'd much prefer the modified question posted on its own and this one kept as it used to be, with additional specification about the permissibility of duplicate values.
    – greybeard
    Aug 29, 2016 at 6:04

2 Answers 2

1

The runtime of O(m*n) is in fact linear, as there are m*n elements in the input. Within a sublinear runtime bound, it is impossible to read every element, which means that without additional assumptions the described algorithm is optimal with respect to runtime complexity.

1
  • Yes you are correct that it's linear approach O(n*m) but is there any way to get it better than this using the fact that columns are sorted. If I get a better solution i will post here. :) Aug 26, 2016 at 13:13
1

(Too lazy to use difference between the maximum and minimum entry in a row, I'll call that range.)
There are a lot of special cases one could take advantage of, one of which kills the apparent trivial worst case of one and the same value for each and every entry, where every row has a range of 0: when a range of 0 is found, searching for a lower one is excessive.
I suggest as a worst case a matrix filled row first with successive values "and extra space around the last one" - starting one column further down every row

 1  2  3  5
11  7  8  9
15 17 13 14

, where the range is the same for every row, a lower range might exist (even with duplicates forbidden) and I don't see how to avoid inspecting each and every entry. For one, my favourite "trick" doesn't work:
For a newly found minimum range candidate, look at the next values in the columns containing the minimum and maximum entries, respectively: while the difference doesn't drop below the candidate, the range can't and rows can be skipped. (Another chance for identical values in a row to mess things up - please specify in the question whether they are permitted.)
Then, there are columns starting with a value that sorts after the last value of all other columns: these contribute row maxima (assuming ascending order). Likewise, columns with a last value to come before the first values of every other contribute row minima. (For unique values, weaker conditions suffice.)

0

Your Answer

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

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