Selection Problem - Matrix

[OnionKnight]

I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution exists. I'm thinking that you are probably misunderstanding the problem, but I'm willing to hear you out.

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.

[arpsmack]

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.

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

.   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

[OnionKnight]

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

.   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

I can't believe I oerlooked that. But thinking about it, I think there's still an O(n) solution. You only have to check 2n - 1 elements. Basically taxicab geometry where you start in the top left and go to the bottom right of the matrix.

[Snafuist]

I think there's still an O(n) solution. You only have to check 2n - 1 elements. Basically taxicab geometry where you start in the top left and go to the bottom right of the matrix.

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:

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

In this case, your algorithm runs in time O(n^2).

Greets,
Philip

[OnionKnight]

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:

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

In this case, your algorithm runs in time O(n^2).

Greets,
Philip

Gah, I didn't think that one all the way through. Yes it wouldn't be possible to know when you've hit the maximum element for a row so I'll rest my O(n) case.