This is a discussion on Selection Problem - Matrix within the Tech Board forums, part of the Community Boards category; Originally Posted by arpsmack I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution ...
Ah ok, that's what I figured you were thinking.
What the problem states is that the *column index* of the maximum element in a row will be less if the row index is less, it doesn't say that the value of the maximum element will be less. The maximum value for the entire matrix could be in any row.
Here's a valid matrix that has its maximum value in the first row (the max value in each row is underlined):
Code:. 0 1 2 3 4 . --------- 0 | 9 7 4 3 2 1 | 8 1 1 2 7 2 | 3 5 2 2 1 3 | 3 3 4 2 6 4 | 1 2 5 4 8 Row | Column Index of Max Value 0 | 0 1 | 0 2 | 1 3 | 4 4 | 4
How do you decide to switch rows? If I'm not mistaken, you want to advance to the next row when you encounter the largest element in the current row. With your approach, you'll have to check all elements to the right of the current one to determine the largest. Now consider the following matrix:
In this case, your algorithm runs in time O(n^2).Code:2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1
Greets,
Philip
All things begin as source code.
Source code begins with an empty file.
-- Tao Te Chip