Help needed: Complexity Big O(n)

[amishosh]

Hi!

I have this really difficult homework assignment. I don't want answers, just perhaps a point in the right direction...I gave this a lot of thought and still nothing :(

I need to find what's called a "sink" in a matrix of all 1s or 0s.
A "sink" is when the Kth row is all 0s and the Kth column is all 1s (aside of mat[k][k] which is 0.

For example:
Mat:
1 0 1 1 0
0 1 1 0 1
0 0 0 0 0
1 0 1 1 1
0 1 1 0 0

This matrix has a "sink" because row 2 is all 0s and column 2 is all 1s (aside from Mat[2][2] which is 0)

Now here's the tricky part:
The algorithm must be of complexity of Big O(n) and not Big O(n²)...
Can some one point me in the right direction here?

[sarehu]

What is n in this case? The number of elements in the matrix, or the width or height of the matrix? Edit: or is it the number of 1's in the matrix plus the width? That would be reasonable, depending on the graph/matrix representation.

Edit: see reply below.

[sarehu]

Never mind, you can do it in O(n) time where you have an n by n matrix. Given any two candidates i and j, you can eliminate one of them by looking at the (i,j) entry. That's a huge hint.

[amishosh]

Given any two candidates i and j

You mean like indexes?

[sarehu]

Yeah. A sink exists when the kth row and column have certain properties, for some value of K where 1 <= k <= n. Let's call each number from 1 to n a "candidate" to be the value of k that is the sink.

[invisal]

int k=0, i=0, c=0;

    while (k < SIZE) {
        c++;
        if (mat[k][i] == 1) {
            k++;
            i = 0;
            continue;
        }

        if (i == SIZE-1) break;
        i++;
    }

Is this a Big O(n)?