There is only one row you'd need to search through as all other rows are guaranteed to have it's maximum value less than it. In the case of equality, it wouldn't matter which of the possible rows you'd pick so you can just search through that row.
Printable View
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